/*
  This source is part of the libosmscout library
  Copyright (C) 2022 Lukas Karas
  Copyright (C) 2016 Mapbox

  ISC License (compatible with GNU LGPL)

  Permission to use, copy, modify, and/or distribute this software for any purpose
  with or without fee is hereby granted, provided that the above copyright notice
  and this permission notice appear in all copies.

  THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH REGARD TO
  THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS.
  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR
  CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA
  OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS
  ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
  SOFTWARE.
 */

/**
 * Some test cases copied from https://github.com/mapbox/polylabel/tree/master/test
 */
#include <osmscout/util/PolygonCenter.h>
#include <osmscout/log/Logger.h>

#include <catch2/catch_test_macros.hpp>

static const std::vector<std::vector<int>> water1Data = {
    std::vector<int>{3116, 3071, 3118, 3068, 3108, 3102, 3100, 3105, 3096, 3113, 3099, 3121, 3091, 3135, 3099, 3133,
                     3105, 3144, 3113, 3144, 3105, 3143, 3117, 3157, 3129, 3155, 3137, 3167, 3152, 3177, 3160, 3187,
                     3172, 3204, 3174, 3195, 3179, 3217, 3197, 3225, 3189, 3217, 3203, 3217, 3199, 3202, 3186, 3188,
                     3186, 3174, 3174, 3166, 3165, 3145, 3168, 3143, 3159, 3143, 3151, 3118, 3154, 3107, 3165, 3110,
                     3174, 3105, 3175, 3082, 3186, 3076, 3178, 3089, 3183, 3103, 3196, 3116, 3181, 3105, 3180, 3111,
                     3155, 3111, 3173, 3130, 3179, 3150, 3197, 3170, 3199, 3178, 3216, 3190, 3214, 3203, 3235, 3219,
                     3243, 3212, 3244, 3198, 3246, 3208, 3244, 3219, 3236, 3240, 3237, 3249, 3248, 3262, 3263, 3267,
                     3327, 3313, 3338, 3327, 3340, 3340, 3351, 3349, 3353, 3361, 3345, 3365, 3355, 3387, 3363, 3392,
                     3364, 3401, 3375, 3413, 3382, 3421, 3394, 3431, 3404, 3433, 3398, 3416, 3406, 3433, 3409, 3422,
                     3428, 3400, 3423, 3392, 3446, 3377, 3461, 3366, 3495, 3354, 3506, 3343, 3506, 3334, 3495, 3338,
                     3505, 3332, 3503, 3323, 3511, 3316, 3512, 3303, 3502, 3302, 3513, 3296, 3509, 3286, 3517, 3283,
                     3525, 3277, 3528, 3269, 3526, 3277, 3526, 3287, 3517, 3288, 3518, 3301, 3515, 3313, 3508, 3329,
                     3517, 3333, 3522, 3341, 3534, 3344, 3547, 3333, 3549, 3323, 3561, 3314, 3565, 3302, 3576, 3301,
                     3573, 3314, 3568, 3329, 3559, 3348, 3543, 3341, 3547, 3362, 3563, 3362, 3573, 3327, 3576, 3309,
                     3583, 3292, 3594, 3256, 3611, 3205, 3599, 3181, 3585, 3172, 3574, 3167, 3583, 3176, 3597, 3193,
                     3583, 3184, 3583, 3192, 3583, 3200, 3576, 3188, 3575, 3198, 3573, 3190, 3557, 3197, 3565, 3205,
                     3564, 3211, 3564, 3224, 3563, 3233, 3565, 3245, 3555, 3240, 3564, 3226, 3558, 3218, 3558, 3210,
                     3549, 3208, 3557, 3202, 3540, 3186, 3539, 3195, 3540, 3204, 3532, 3198, 3530, 3209, 3528, 3222,
                     3516, 3220, 3515, 3235, 3503, 3239, 3503, 3241, 3495, 3241, 3497, 3249, 3489, 3260, 3478, 3271,
                     3477, 3281, 3478, 3272, 3482, 3253, 3470, 3248, 3481, 3245, 3488, 3230, 3496, 3232, 3509, 3221,
                     3515, 3199, 3502, 3197, 3493, 3189, 3488, 3181, 3478, 3174, 3470, 3185, 3474, 3172, 3470, 3162,
                     3461, 3170, 3452, 3169, 3449, 3160, 3464, 3158, 3456, 3146, 3464, 3154, 3476, 3153, 3470, 3145,
                     3488, 3161, 3504, 3182, 3511, 3171, 3522, 3166, 3533, 3168, 3541, 3169, 3537, 3158, 3545, 3152,
                     3544, 3163, 3553, 3159, 3578, 3138, 3570, 3127, 3561, 3128, 3561, 3120, 3552, 3119, 3518, 3101,
                     3509, 3090, 3508, 3085, 3517, 3085, 3508, 3079, 3506, 3071, 3512, 3056, 3495, 3053, 3481, 3056,
                     3478, 3066, 3491, 3073, 3497, 3099, 3493, 3091, 3467, 3086, 3470, 3096, 3476, 3104, 3484, 3106,
                     3474, 3108, 3484, 3124, 3472, 3116, 3464, 3116, 3468, 3107, 3464, 3099, 3452, 3108, 3448, 3120,
                     3448, 3112, 3440, 3114, 3449, 3108, 3440, 3108, 3457, 3103, 3461, 3090, 3453, 3089, 3452, 3099,
                     3437, 3103, 3453, 3083, 3435, 3077, 3432, 3087, 3424, 3087, 3425, 3077, 3413, 3082, 3407, 3090,
                     3413, 3102, 3405, 3102, 3406, 3116, 3403, 3094, 3392, 3092, 3386, 3101, 3382, 3118, 3385, 3130,
                     3380, 3119, 3354, 3116, 3378, 3115, 3377, 3107, 3367, 3098, 3376, 3100, 3378, 3092, 3386, 3092,
                     3375, 3084, 3374, 3071, 3381, 3082, 3397, 3081, 3398, 3072, 3407, 3061, 3398, 3055, 3406, 3057,
                     3411, 3045, 3402, 3042, 3397, 3033, 3383, 3037, 3375, 3035, 3367, 3038, 3358, 3047, 3348, 3040,
                     3356, 3041, 3359, 3033, 3372, 3034, 3368, 3024, 3375, 3032, 3385, 3029, 3383, 3018, 3379, 3010,
                     3389, 3025, 3397, 3024, 3419, 3040, 3419, 3023, 3427, 3034, 3431, 3043, 3436, 3029, 3422, 3010,
                     3435, 3021, 3436, 3008, 3414, 2983, 3417, 2995, 3413, 3008, 3406, 3000, 3407, 2992, 3384, 2994,
                     3378, 3003, 3378, 2994, 3367, 2995, 3348, 2988, 3373, 2990, 3383, 2990, 3387, 2985, 3397, 2985,
                     3395, 2975, 3390, 2964, 3368, 2965, 3328, 2969, 3326, 2977, 3324, 2985, 3326, 3001, 3319, 2988,
                     3314, 2997, 3319, 2986, 3311, 2984, 3321, 2974, 3313, 2978, 3305, 2979, 3295, 2982, 3289, 2970,
                     3297, 2977, 3321, 2973, 3285, 2952, 3264, 2928, 3239, 2921, 3203, 2882, 3194, 2873, 3190, 2882,
                     3184, 2892, 3184, 2883, 3189, 2880, 3179, 2880, 3191, 2877, 3152, 2864, 3160, 2878, 3164, 2890,
                     3166, 2902, 3158, 2907, 3163, 2891, 3151, 2882, 3151, 2873, 3151, 2855, 3137, 2864, 3129, 2860,
                     3119, 2869, 3128, 2859, 3142, 2850, 3153, 2849, 3158, 2858, 3155, 2848, 3133, 2837, 3114, 2818,
                     3094, 2819, 3071, 2818, 3079, 2816, 3108, 2809, 3081, 2774, 3072, 2753, 3050, 2728, 3044, 2711,
                     3043, 2694, 3028, 2690, 3024, 2679, 2993, 2629, 2965, 2604, 2950, 2584, 2919, 2559, 2909, 2528,
                     2896, 2507, 2894, 2482, 2883, 2474, 2837, 2458, 2831, 2438, 2835, 2413, 2846, 2402, 2867, 2396,
                     2871, 2429, 2879, 2431, 2893, 2446, 2908, 2456, 2916, 2454, 2915, 2462, 2921, 2458, 2921, 2466,
                     2933, 2479, 2948, 2508, 2953, 2528, 2969, 2552, 2977, 2545, 2983, 2537, 3002, 2542, 3006, 2550,
                     2997, 2553, 2989, 2549, 2985, 2541, 2987, 2551, 2985, 2566, 2992, 2579, 3001, 2575, 3009, 2575,
                     3018, 2574, 3010, 2576, 3000, 2577, 3000, 2592, 3016, 2602, 3028, 2613, 3038, 2609, 3040, 2599,
                     3040, 2608, 3050, 2609, 3048, 2621, 3061, 2620, 3053, 2618, 3047, 2631, 3058, 2650, 3073, 2662,
                     3098, 2699, 3105, 2704, 3113, 2704, 3121, 2730, 3129, 2733, 3141, 2747, 3142, 2730, 3151, 2735,
                     3143, 2740, 3145, 2752, 3143, 2763, 3167, 2789, 3162, 2777, 3185, 2754, 3174, 2766, 3182, 2791,
                     3188, 2781, 3189, 2796, 3199, 2796, 3213, 2777, 3205, 2791, 3193, 2803, 3191, 2815, 3196, 2826,
                     3197, 2807, 3208, 2815, 3205, 2824, 3213, 2823, 3203, 2827, 3212, 2834, 3224, 2832, 3218, 2821,
                     3226, 2827, 3226, 2819, 3225, 2790, 3230, 2801, 3233, 2799, 3233, 2821, 3227, 2837, 3226, 2849,
                     3239, 2846, 3247, 2848, 3259, 2865, 3269, 2916, 3305, 2899, 3302, 2889, 3293, 2891, 3295, 2883,
                     3296, 2875, 3297, 2884, 3307, 2882, 3306, 2890, 3316, 2890, 3321, 2882, 3329, 2881, 3328, 2888,
                     3343, 2888, 3329, 2890, 3317, 2894, 3305, 2902, 3318, 2906, 3327, 2908, 3367, 2899, 3388, 2886,
                     3386, 2878, 3378, 2880, 3367, 2878, 3368, 2870, 3379, 2864, 3383, 2876, 3391, 2882, 3401, 2872,
                     3401, 2881, 3430, 2880, 3438, 2885, 3439, 2873, 3427, 2875, 3417, 2868, 3441, 2869, 3442, 2853,
                     3437, 2832, 3424, 2828, 3438, 2827, 3427, 2825, 3431, 2815, 3420, 2824, 3415, 2836, 3415, 2825,
                     3425, 2816, 3414, 2817, 3422, 2811, 3433, 2808, 3426, 2794, 3408, 2799, 3425, 2803, 3395, 2803,
                     3389, 2816, 3394, 2802, 3380, 2796, 3381, 2807, 3370, 2802, 3365, 2812, 3370, 2816, 3362, 2816,
                     3368, 2825, 3359, 2823, 3350, 2818, 3348, 2835, 3356, 2846, 3345, 2833, 3336, 2843, 3328, 2844,
                     3318, 2847, 3329, 2841, 3338, 2831, 3336, 2816, 3327, 2813, 3319, 2815, 3328, 2808, 3337, 2808,
                     3355, 2808, 3359, 2799, 3343, 2801, 3352, 2795, 3346, 2790, 3356, 2790, 3367, 2791, 3353, 2779,
                     3349, 2783, 3340, 2783, 3331, 2793, 3319, 2783, 3295, 2799, 3299, 2791, 3319, 2780, 3315, 2769,
                     3306, 2770, 3310, 2751, 3300, 2746, 3301, 2738, 3313, 2746, 3317, 2758, 3317, 2767, 3323, 2777,
                     3331, 2776, 3345, 2775, 3336, 2774, 3343, 2760, 3351, 2762, 3356, 2762, 3356, 2748, 3363, 2757,
                     3363, 2768, 3367, 2776, 3375, 2776, 3370, 2758, 3381, 2774, 3391, 2778, 3399, 2779, 3407, 2772,
                     3400, 2764, 3398, 2753, 3402, 2744, 3385, 2729, 3373, 2717, 3358, 2695, 3357, 2704, 3360, 2719,
                     3350, 2715, 3352, 2705, 3338, 2709, 3335, 2701, 3327, 2696, 3317, 2706, 3309, 2704, 3294, 2708,
                     3303, 2699, 3295, 2693, 3297, 2680, 3301, 2683, 3301, 2691, 3306, 2699, 3319, 2697, 3322, 2681,
                     3324, 2671, 3328, 2667, 3328, 2659, 3327, 2648, 3315, 2651, 3312, 2643, 3300, 2645, 3292, 2633,
                     3278, 2629, 3289, 2630, 3285, 2621, 3284, 2608, 3294, 2620, 3307, 2636, 3316, 2629, 3320, 2641,
                     3329, 2640, 3337, 2639, 3341, 2653, 3350, 2655, 3349, 2660, 3349, 2669, 3381, 2667, 3390, 2680,
                     3401, 2691, 3411, 2689, 3408, 2679, 3397, 2670, 3399, 2644, 3391, 2648, 3394, 2640, 3385, 2640,
                     3389, 2631, 3397, 2636, 3401, 2628, 3399, 2616, 3375, 2612, 3364, 2627, 3371, 2610, 3353, 2606,
                     3329, 2611, 3346, 2599, 3334, 2590, 3347, 2592, 3346, 2578, 3338, 2569, 3350, 2570, 3354, 2559,
                     3344, 2544, 3359, 2538, 3360, 2531, 3370, 2531, 3367, 2539, 3356, 2542, 3361, 2560, 3364, 2573,
                     3354, 2580, 3360, 2593, 3377, 2597, 3384, 2589, 3394, 2599, 3405, 2601, 3418, 2599, 3399, 2582,
                     3407, 2577, 3400, 2559, 3409, 2572, 3410, 2581, 3421, 2585, 3426, 2574, 3420, 2588, 3432, 2583,
                     3429, 2592, 3425, 2602, 3428, 2615, 3436, 2615, 3428, 2619, 3427, 2630, 3437, 2630, 3434, 2639,
                     3434, 2650, 3442, 2658, 3452, 2649, 3444, 2661, 3453, 2665, 3457, 2656, 3454, 2664, 3465, 2667,
                     3468, 2659, 3466, 2670, 3470, 2679, 3482, 2674, 3480, 2684, 3489, 2685, 3498, 2687, 3491, 2678,
                     3501, 2679, 3505, 2668, 3507, 2653, 3500, 2643, 3493, 2633, 3485, 2636, 3494, 2632, 3485, 2629,
                     3488, 2619, 3496, 2614, 3493, 2603, 3478, 2605, 3479, 2595, 3470, 2593, 3472, 2582, 3470, 2565,
                     3479, 2559, 3482, 2550, 3474, 2548, 3482, 2547, 3490, 2542, 3487, 2557, 3478, 2571, 3477, 2584,
                     3484, 2594, 3492, 2596, 3500, 2582, 3497, 2593, 3501, 2602, 3512, 2604, 3516, 2596, 3520, 2587,
                     3530, 2577, 3523, 2591, 3523, 2600, 3514, 2604, 3516, 2612, 3500, 2627, 3512, 2629, 3511, 2637,
                     3519, 2635, 3518, 2644, 3533, 2642, 3519, 2654, 3532, 2657, 3524, 2660, 3526, 2670, 3518, 2669,
                     3518, 2677, 3516, 2689, 3514, 2701, 3525, 2717, 3533, 2718, 3538, 2726, 3540, 2737, 3549, 2734,
                     3560, 2720, 3567, 2728, 3556, 2732, 3559, 2742, 3551, 2739, 3558, 2764, 3570, 2767, 3570, 2759,
                     3579, 2759, 3571, 2766, 3583, 2774, 3594, 2769, 3594, 2783, 3603, 2800, 3609, 2787, 3610, 2762,
                     3601, 2769, 3598, 2765, 3598, 2754, 3596, 2738, 3597, 2748, 3609, 2748, 3606, 2732, 3598, 2725,
                     3609, 2718, 3600, 2719, 3599, 2709, 3589, 2706, 3579, 2715, 3581, 2704, 3577, 2704, 3569, 2704,
                     3563, 2690, 3553, 2693, 3544, 2679, 3554, 2690, 3562, 2689, 3570, 2697, 3580, 2698, 3592, 2702,
                     3604, 2698, 3607, 2688, 3608, 2700, 3621, 2697, 3619, 2711, 3632, 2698, 3629, 2685, 3631, 2677,
                     3619, 2676, 3610, 2682, 3605, 2673, 3593, 2678, 3585, 2668, 3601, 2672, 3599, 2660, 3608, 2672,
                     3609, 2657, 3600, 2652, 3613, 2660, 3622, 2669, 3630, 2671, 3642, 2673, 3633, 2684, 3644, 2679,
                     3645, 2653, 3637, 2654, 3620, 2651, 3615, 2641, 3627, 2650, 3635, 2650, 3630, 2638, 3632, 2623,
                     3642, 2619, 3635, 2561, 3624, 2537, 3622, 2551, 3620, 2541, 3615, 2550, 3608, 2558, 3607, 2528,
                     3617, 2529, 3600, 2513, 3595, 2527, 3601, 2539, 3589, 2554, 3590, 2542, 3589, 2534, 3586, 2522,
                     3563, 2523, 3562, 2531, 3554, 2543, 3554, 2531, 3561, 2522, 3550, 2519, 3544, 2527, 3548, 2517,
                     3560, 2518, 3568, 2519, 3581, 2516, 3585, 2503, 3598, 2501, 3573, 2481, 3565, 2490, 3554, 2492,
                     3563, 2484, 3568, 2474, 3547, 2476, 3526, 2474, 3517, 2477, 3507, 2479, 3493, 2475, 3484, 2471,
                     3495, 2474, 3508, 2477, 3508, 2468, 3517, 2474, 3523, 2466, 3518, 2443, 3497, 2443, 3489, 2439,
                     3480, 2421, 3481, 2410, 3467, 2413, 3459, 2408, 3447, 2407, 3437, 2399, 3424, 2400, 3428, 2409,
                     3430, 2421, 3427, 2413, 3419, 2411, 3418, 2396, 3411, 2409, 3414, 2422, 3402, 2436, 3387, 2439,
                     3376, 2431, 3361, 2432, 3347, 2423, 3317, 2429, 3334, 2417, 3329, 2401, 3311, 2404, 3301, 2397,
                     3301, 2387, 3293, 2389, 3283, 2383, 3271, 2387, 3268, 2395, 3272, 2377, 3260, 2365, 3249, 2364,
                     3240, 2366, 3231, 2347, 3222, 2347, 3209, 2346, 3212, 2334, 3204, 2330, 3200, 2350, 3190, 2349,
                     3184, 2339, 3170, 2340, 3166, 2332, 3155, 2322, 3161, 2311, 3147, 2306, 3142, 2291, 3149, 2303,
                     3166, 2307, 3174, 2317, 3169, 2327, 3182, 2330, 3196, 2339, 3195, 2331, 3201, 2325, 3211, 2325,
                     3218, 2331, 3218, 2339, 3233, 2339, 3243, 2357, 3256, 2355, 3254, 2340, 3262, 2343, 3268, 2359,
                     3277, 2353, 3278, 2366, 3280, 2378, 3291, 2381, 3308, 2374, 3319, 2387, 3335, 2392, 3342, 2407,
                     3350, 2407, 3359, 2413, 3359, 2404, 3369, 2396, 3380, 2397, 3385, 2406, 3390, 2428, 3402, 2421,
                     3397, 2410, 3400, 2382, 3401, 2384, 3401, 2407, 3402, 2412, 3402, 2398, 3411, 2376, 3422, 2375,
                     3434, 2386, 3430, 2378, 3432, 2369, 3444, 2362, 3432, 2371, 3435, 2379, 3464, 2378, 3479, 2387,
                     3491, 2382, 3502, 2383, 3510, 2380, 3513, 2371, 3522, 2373, 3524, 2403, 3528, 2369, 3517, 2371,
                     3509, 2367, 3509, 2357, 3515, 2366, 3524, 2364, 3518, 2353, 3531, 2364, 3533, 2352, 3537, 2363,
                     3546, 2366, 3554, 2363, 3554, 2355, 3566, 2354, 3571, 2344, 3598, 2233, 3579, 2200, 3566, 2194,
                     3546, 2192, 3554, 2193, 3554, 2207, 3543, 2208, 3541, 2217, 3520, 2210, 3488, 2216, 3485, 2205,
                     3477, 2200, 3467, 2190, 3481, 2203, 3496, 2201, 3499, 2209, 3511, 2200, 3522, 2207, 3520, 2190,
                     3520, 2178, 3511, 2168, 3505, 2180, 3505, 2172, 3492, 2171, 3473, 2167, 3486, 2168, 3498, 2168,
                     3510, 2164, 3517, 2152, 3514, 2147, 3506, 2147, 3500, 2156, 3506, 2143, 3495, 2141, 3488, 2153,
                     3487, 2145, 3494, 2137, 3485, 2140, 3485, 2133, 3476, 2133, 3486, 2128, 3475, 2121, 3471, 2117,
                     3460, 2117, 3472, 2115, 3472, 2106, 3473, 2119, 3482, 2117, 3484, 2125, 3496, 2124, 3497, 2132,
                     3505, 2134, 3503, 2123, 3509, 2134, 3513, 2126, 3518, 2128, 3518, 2137, 3526, 2132, 3519, 2115,
                     3509, 2110, 3498, 2108, 3498, 2096, 3492, 2101, 3481, 2101, 3491, 2098, 3496, 2087, 3487, 2088,
                     3495, 2081, 3482, 2070, 3496, 2080, 3500, 2065, 3490, 2056, 3500, 2056, 3508, 2059, 3506, 2067,
                     3498, 2076, 3498, 2091, 3507, 2088, 3505, 2097, 3517, 2100, 3519, 2092, 3518, 2103, 3527, 2108,
                     3526, 2093, 3538, 2092, 3534, 2100, 3542, 2105, 3550, 2110, 3544, 2102, 3549, 2090, 3540, 2077,
                     3549, 2082, 3552, 2090, 3557, 2103, 3566, 2086, 3561, 2073, 3556, 2064, 3552, 2066, 3552, 2051,
                     3542, 2053, 3533, 2049, 3543, 2051, 3537, 2042, 3540, 2034, 3531, 2029, 3522, 2028, 3513, 2035,
                     3525, 2023, 3536, 2025, 3526, 2013, 3512, 2006, 3508, 2017, 3500, 2020, 3508, 2012, 3516, 2003,
                     3502, 1994, 3514, 1989, 3517, 1983, 3517, 1975, 3516, 1967, 3508, 1962, 3517, 1962, 3519, 1973,
                     3516, 1997, 3527, 2002, 3536, 2003, 3534, 2011, 3549, 2017, 3558, 2026, 3556, 2007, 3548, 2004,
                     3545, 1994, 3553, 1978, 3544, 1966, 3535, 1967, 3531, 1959, 3539, 1959, 3555, 1966, 3555, 1944,
                     3542, 1942, 3560, 1943, 3571, 1931, 3581, 1927, 3586, 1940, 3590, 1931, 3574, 1929, 3560, 1921,
                     3555, 1932, 3539, 1935, 3546, 1927, 3538, 1924, 3544, 1916, 3530, 1914, 3520, 1913, 3512, 1913,
                     3508, 1903, 3496, 1897, 3485, 1904, 3490, 1895, 3503, 1892, 3512, 1906, 3527, 1911, 3541, 1909,
                     3551, 1914, 3552, 1905, 3538, 1895, 3556, 1904, 3558, 1878, 3548, 1878, 3539, 1878, 3528, 1875,
                     3518, 1870, 3529, 1872, 3525, 1861, 3541, 1869, 3551, 1872, 3559, 1857, 3543, 1861, 3539, 1851,
                     3534, 1838, 3521, 1847, 3531, 1841, 3522, 1837, 3532, 1837, 3525, 1826, 3528, 1818, 3518, 1812,
                     3505, 1820, 3497, 1818, 3510, 1825, 3502, 1840, 3504, 1829, 3491, 1826, 3490, 1814, 3483, 1826,
                     3471, 1841, 3473, 1833, 3473, 1823, 3481, 1813, 3472, 1818, 3459, 1816, 3453, 1810, 3453, 1818,
                     3445, 1815, 3436, 1822, 3432, 1812, 3454, 1807, 3465, 1806, 3460, 1795, 3454, 1784, 3445, 1790,
                     3443, 1781, 3434, 1784, 3423, 1781, 3431, 1775, 3418, 1777, 3400, 1769, 3402, 1777, 3390, 1773,
                     3379, 1765, 3370, 1766, 3364, 1753, 3375, 1755, 3386, 1766, 3395, 1767, 3408, 1765, 3418, 1770,
                     3434, 1766, 3437, 1758, 3443, 1767, 3439, 1776, 3448, 1779, 3458, 1777, 3469, 1784, 3472, 1779,
                     3472, 1764, 3473, 1774, 3472, 1782, 3473, 1800, 3472, 1809, 3480, 1797, 3503, 1806, 3499, 1791,
                     3509, 1789, 3506, 1802, 3527, 1796, 3532, 1808, 3543, 1798, 3551, 1795, 3540, 1804, 3548, 1807,
                     3541, 1825, 3547, 1827, 3547, 1842, 3547, 1823, 3559, 1807, 3555, 1819, 3553, 1829, 3554, 1837,
                     3564, 1837, 3568, 1825, 3572, 1834, 3580, 1837, 3575, 1839, 3575, 1849, 3583, 1859, 3593, 1858,
                     3593, 1842, 3597, 1834, 3589, 1831, 3582, 1821, 3590, 1826, 3593, 1810, 3585, 1807, 3584, 1796,
                     3593, 1793, 3591, 1801, 3605, 1804, 3595, 1812, 3597, 1821, 3598, 1829, 3606, 1819, 3615, 1815,
                     3611, 1825, 3619, 1822, 3614, 1831, 3605, 1826, 3612, 1836, 3604, 1831, 3602, 1839, 3607, 1854,
                     3603, 1864, 3595, 1865, 3597, 1875, 3606, 1874, 3619, 1866, 3616, 1855, 3624, 1858, 3621, 1847,
                     3623, 1839, 3628, 1848, 3639, 1835, 3641, 1811, 3632, 1816, 3642, 1807, 3626, 1806, 3634, 1802,
                     3644, 1801, 3660, 1733, 3651, 1755, 3640, 1770, 3643, 1762, 3646, 1752, 3644, 1740, 3638, 1751,
                     3630, 1748, 3637, 1744, 3637, 1734, 3626, 1738, 3605, 1744, 3608, 1756, 3619, 1757, 3618, 1767,
                     3608, 1758, 3609, 1770, 3605, 1754, 3600, 1771, 3592, 1766, 3596, 1758, 3600, 1737, 3588, 1746,
                     3591, 1736, 3579, 1738, 3565, 1734, 3573, 1729, 3561, 1717, 3552, 1723, 3559, 1714, 3555, 1704,
                     3547, 1696, 3538, 1694, 3548, 1694, 3553, 1685, 3550, 1694, 3556, 1702, 3567, 1698, 3559, 1708,
                     3563, 1717, 3576, 1713, 3577, 1722, 3583, 1732, 3600, 1729, 3592, 1713, 3597, 1722, 3605, 1734,
                     3615, 1732, 3618, 1724, 3604, 1710, 3599, 1702, 3613, 1714, 3621, 1712, 3620, 1721, 3631, 1723,
                     3640, 1723, 3648, 1728, 3661, 1732, 3640, 1721, 3619, 1694, 3516, 1632, 3453, 1610, 3456, 1619,
                     3458, 1628, 3449, 1613, 3446, 1622, 3441, 1634, 3455, 1642, 3446, 1647, 3449, 1661, 3438, 1671,
                     3449, 1673, 3456, 1682, 3444, 1688, 3453, 1680, 3440, 1676, 3430, 1676, 3446, 1660, 3440, 1652,
                     3438, 1642, 3430, 1645, 3438, 1641, 3422, 1639, 3422, 1631, 3442, 1621, 3426, 1621, 3428, 1616,
                     3436, 1616, 3445, 1610, 3421, 1602, 3420, 1611, 3420, 1601, 3403, 1594, 3406, 1602, 3404, 1611,
                     3396, 1622, 3403, 1632, 3398, 1624, 3387, 1616, 3395, 1616, 3397, 1608, 3389, 1608, 3389, 1599,
                     3403, 1593, 3385, 1573, 3377, 1568, 3373, 1581, 3377, 1589, 3374, 1593, 3374, 1585, 3372, 1576,
                     3363, 1572, 3356, 1582, 3358, 1573, 3366, 1567, 3359, 1554, 3350, 1562, 3334, 1554, 3341, 1563,
                     3341, 1588, 3323, 1598, 3317, 1588, 3307, 1601, 3315, 1612, 3305, 1605, 3305, 1615, 3300, 1624,
                     3305, 1626, 3305, 1644, 3296, 1645, 3286, 1656, 3295, 1648, 3301, 1638, 3297, 1627, 3299, 1612,
                     3287, 1608, 3275, 1617, 3290, 1604, 3303, 1608, 3304, 1598, 3315, 1583, 3303, 1587, 3313, 1579,
                     3325, 1582, 3331, 1566, 3315, 1569, 3318, 1558, 3310, 1561, 3312, 1552, 3300, 1550, 3296, 1562,
                     3292, 1552, 3281, 1551, 3282, 1562, 3274, 1565, 3269, 1575, 3272, 1565, 3263, 1568, 3264, 1565,
                     3255, 1565, 3269, 1563, 3277, 1562, 3275, 1546, 3265, 1547, 3264, 1537, 3274, 1542, 3284, 1546,
                     3288, 1536, 3293, 1547, 3297, 1537, 3308, 1543, 3318, 1541, 3298, 1531, 3306, 1526, 3301, 1514,
                     3313, 1516, 3311, 1527, 3322, 1526, 3327, 1535, 3331, 1535, 3331, 1520, 3323, 1520, 3314, 1511,
                     3306, 1510, 3320, 1504, 3276, 1492, 3255, 1480, 3224, 1481, 3240, 1492, 3224, 1490, 3224, 1499,
                     3222, 1507, 3231, 1504, 3231, 1516, 3223, 1522, 3239, 1524, 3230, 1526, 3222, 1526, 3218, 1537,
                     3220, 1545, 3224, 1555, 3225, 1569, 3217, 1558, 3215, 1549, 3219, 1541, 3206, 1544, 3212, 1535,
                     3211, 1527, 3218, 1517, 3205, 1514, 3198, 1522, 3186, 1524, 3176, 1531, 3182, 1522, 3185, 1516,
                     3193, 1516, 3204, 1509, 3202, 1501, 3214, 1507, 3211, 1491, 3199, 1493, 3190, 1503, 3193, 1495,
                     3196, 1484, 3188, 1481, 3180, 1486, 3173, 1482, 3173, 1498, 3160, 1504, 3156, 1514, 3143, 1524,
                     3154, 1514, 3158, 1505, 3170, 1495, 3167, 1483, 3161, 1481, 3169, 1481, 3168, 1473, 3158, 1468,
                     3150, 1466, 3158, 1465, 3171, 1475, 3181, 1477, 3177, 1469, 3186, 1476, 3194, 1476, 3205, 1475,
                     3202, 1457, 3194, 1451, 3190, 1460, 3192, 1450, 3184, 1454, 3183, 1446, 3171, 1440, 3185, 1439,
                     3193, 1446, 3190, 1436, 3188, 1426, 3190, 1414, 3194, 1425, 3199, 1436, 3204, 1448, 3208, 1457,
                     3220, 1459, 3217, 1447, 3235, 1444, 3244, 1445, 3227, 1412, 3223, 1389, 3186, 1367, 3158, 1353,
                     3158, 1372, 3147, 1369, 3145, 1383, 3143, 1375, 3150, 1363, 3158, 1350, 3136, 1332, 3138, 1340,
                     3132, 1337, 3132, 1346, 3128, 1336, 3117, 1348, 3118, 1340, 3127, 1336, 3135, 1332, 3126, 1320,
                     3109, 1322, 3109, 1331, 3105, 1319, 3106, 1311, 3108, 1321, 3120, 1317, 3116, 1308, 3126, 1318,
                     3126, 1309, 3130, 1320, 3125, 1288, 3113, 1271, 3115, 1255, 3090, 1247, 3072, 1252, 3071, 1265,
                     3084, 1266, 3084, 1297, 3074, 1305, 3083, 1300, 3083, 1308, 3080, 1324, 3078, 1335, 3066, 1334,
                     3063, 1342, 3065, 1357, 3059, 1348, 3047, 1347, 3046, 1355, 3046, 1344, 3023, 1344, 3034, 1343,
                     3052, 1344, 3049, 1336, 3061, 1333, 3069, 1328, 3071, 1320, 3071, 1303, 3066, 1293, 3056, 1295,
                     3057, 1306, 3043, 1309, 3054, 1297, 3042, 1300, 3055, 1292, 3057, 1286, 3043, 1286, 3056, 1282,
                     3048, 1278, 3036, 1255, 3025, 1249, 3008, 1240, 3003, 1234, 2984, 1234, 2981, 1253, 2954, 1274,
                     2977, 1258, 2984, 1267, 2971, 1269, 2980, 1273, 2975, 1286, 2988, 1280, 2990, 1289, 3007, 1293,
                     2995, 1291, 2993, 1302, 2992, 1293, 2982, 1289, 2984, 1297, 2970, 1288, 2968, 1277, 2965, 1291,
                     2964, 1300, 2976, 1304, 2975, 1319, 2971, 1331, 2965, 1340, 2957, 1342, 2942, 1338, 2938, 1353,
                     2949, 1368, 2953, 1376, 2962, 1390, 2972, 1389, 2983, 1398, 2986, 1407, 2994, 1410, 2983, 1409,
                     2975, 1396, 2950, 1384, 2939, 1386, 2950, 1380, 2934, 1360, 2931, 1351, 2932, 1343, 2921, 1341,
                     2906, 1338, 2937, 1337, 2942, 1329, 2953, 1332, 2959, 1323, 2948, 1315, 2961, 1320, 2952, 1311,
                     2953, 1294, 2930, 1282, 2923, 1291, 2929, 1281, 2920, 1277, 2917, 1265, 2909, 1258, 2898, 1255,
                     2889, 1265, 2898, 1246, 2885, 1237, 2883, 1246, 2875, 1243, 2879, 1246, 2879, 1238, 2876, 1222,
                     2840, 1217, 2804, 1226, 2783, 1227, 2760, 1220, 2754, 1212, 2728, 1209, 2688, 1174, 2681, 1194,
                     2673, 1197, 2666, 1212, 2663, 1197, 2669, 1197, 2669, 1189, 2675, 1178, 2684, 1170, 2670, 1160,
                     2640, 1155, 2619, 1142, 2609, 1149, 2596, 1150, 2587, 1147, 2583, 1137, 2576, 1144, 2576, 1153,
                     2568, 1157, 2561, 1149, 2544, 1154, 2534, 1161, 2525, 1161, 2538, 1160, 2539, 1150, 2558, 1148,
                     2567, 1145, 2572, 1136, 2585, 1123, 2602, 1137, 2603, 1126, 2597, 1111, 2598, 1102, 2589, 1101,
                     2590, 1093, 2591, 1082, 2593, 1069, 2585, 1072, 2583, 1080, 2574, 1074, 2583, 1076, 2591, 1062,
                     2601, 1074, 2601, 1082, 2602, 1093, 2600, 1104, 2609, 1098, 2611, 1080, 2604, 1054, 2578, 1023,
                     2544, 1023, 2530, 1027, 2529, 1033, 2505, 1033, 2526, 1027, 2535, 1019, 2537, 1012, 2546, 1012,
                     2523, 975, 2515, 980, 2511, 969, 2506, 953, 2486, 957, 2472, 945, 2457, 942, 2456, 933, 2465, 935,
                     2463, 918, 2463, 902, 2474, 931, 2486, 931, 2492, 938, 2502, 938, 2515, 931, 2518, 918, 2527, 912,
                     2524, 896, 2528, 864, 2525, 842, 2488, 787, 2467, 794, 2447, 827, 2432, 843, 2412, 850, 2395, 845,
                     2373, 849, 2348, 848, 2317, 884, 2289, 897, 2251, 898, 2196, 916, 2162, 913, 2141, 901, 2129, 864,
                     2117, 844, 2086, 819, 2090, 808, 2087, 796, 2095, 793, 2084, 755, 2078, 716, 2073, 707, 2079, 661,
                     2097, 610, 2112, 596, 2108, 580, 2133, 565, 2136, 550, 2127, 550, 2142, 539, 2146, 514, 2174, 488,
                     2166, 472, 2162, 452, 2165, 443, 2173, 447, 2190, 428, 2257, 380, 2270, 380, 2282, 415, 2269, 444,
                     2243, 473, 2247, 483, 2256, 486, 2277, 475, 2272, 467, 2281, 454, 2288, 462, 2299, 446, 2312, 443,
                     2314, 434, 2326, 435, 2337, 425, 2345, 427, 2350, 438, 2341, 439, 2334, 447, 2325, 442, 2315, 455,
                     2301, 455, 2305, 466, 2299, 480, 2285, 473, 2286, 484, 2274, 492, 2266, 487, 2260, 498, 2234, 498,
                     2205, 503, 2190, 534, 2196, 523, 2209, 514, 2217, 518, 2217, 509, 2220, 518, 2210, 523, 2215, 533,
                     2201, 541, 2191, 547, 2177, 554, 2174, 569, 2165, 580, 2149, 636, 2162, 651, 2163, 659, 2155, 668,
                     2166, 690, 2162, 707, 2175, 728, 2162, 757, 2188, 823, 2234, 856, 2250, 861, 2278, 852, 2296, 836,
                     2308, 833, 2320, 821, 2351, 803, 2364, 785, 2368, 768, 2395, 776, 2415, 773, 2437, 742, 2447, 739,
                     2487, 706, 2485, 697, 2471, 699, 2468, 696, 2468, 704, 2457, 708, 2463, 700, 2464, 692, 2474, 691,
                     2483, 685, 2490, 664, 2486, 650, 2490, 639, 2506, 627, 2512, 612, 2510, 592, 2517, 611, 2513, 636,
                     2509, 647, 2501, 645, 2503, 656, 2504, 671, 2511, 685, 2520, 693, 2546, 745, 2550, 768, 2559, 790,
                     2568, 799, 2568, 813, 2573, 857, 2585, 874, 2585, 886, 2580, 896, 2596, 896, 2625, 914, 2618, 901,
                     2635, 906, 2648, 901, 2637, 910, 2634, 919, 2651, 931, 2658, 943, 2677, 950, 2686, 930, 2680, 950,
                     2685, 960, 2703, 960, 2688, 962, 2704, 982, 2694, 977, 2680, 969, 2678, 960, 2662, 950, 2656, 983,
                     2659, 992, 2683, 994, 2731, 1023, 2717, 1013, 2716, 994, 2718, 1012, 2730, 1020, 2738, 1019, 2748,
                     1027, 2744, 1019, 2753, 1024, 2767, 1036, 2778, 1035, 2841, 1066, 2856, 1060, 2849, 1045, 2856,
                     1034, 2855, 1056, 2872, 1068, 2855, 1063, 2860, 1074, 2869, 1074, 2876, 1093, 2870, 1104, 2878,
                     1109, 2887, 1109, 2902, 1110, 2911, 1118, 2920, 1108, 2922, 1100, 2909, 1094, 2898, 1094, 2894,
                     1086, 2892, 1073, 2897, 1084, 2903, 1083, 2903, 1092, 2913, 1090, 2922, 1095, 2942, 1065, 2934,
                     1069, 2940, 1061, 2933, 1051, 2925, 1050, 2915, 1046, 2924, 1041, 2933, 1044, 2946, 1044, 2947,
                     1059, 2955, 1058, 2955, 1046, 2967, 1037, 2959, 1030, 2941, 1025, 2958, 1028, 2956, 1017, 2948,
                     1014, 2960, 1013, 2961, 999, 2947, 988, 2932, 989, 2938, 981, 2948, 984, 2952, 976, 2952, 966,
                     2942, 953, 2943, 938, 2948, 940, 2948, 950, 2959, 959, 2962, 973, 2964, 983, 2975, 985, 2975, 994,
                     2978, 1001, 2987, 1001, 2979, 1002, 2978, 1016, 2972, 1025, 2980, 1031, 2984, 1042, 2976, 1052,
                     2979, 1063, 2953, 1082, 2957, 1097, 2979, 1096, 2988, 1084, 2989, 1071, 2991, 1055, 2986, 1047,
                     2997, 1046, 3014, 1049, 3014, 1040, 3010, 1036, 3019, 1036, 3022, 1045, 3037, 1051, 3052, 1042,
                     3054, 1033, 3069, 1031, 3077, 1024, 3084, 1012, 3072, 1007, 3064, 1006, 3056, 995, 3061, 998, 3071,
                     998, 3083, 999, 3092, 1002, 3096, 1011, 3087, 1025, 3088, 1046, 3083, 1037, 3073, 1037, 3068, 1046,
                     3056, 1068, 3036, 1075, 3028, 1075, 3004, 1085, 3006, 1097, 3031, 1096, 3057, 1110, 3073, 1112,
                     3073, 1112, 3088, 1112, 3145, 1132, 3142, 1129, 3160, 1129, 3147, 1133, 3172, 1154, 3196, 1139,
                     3183, 1148, 3174, 1155, 3199, 1181, 3204, 1202, 3208, 1200, 3208, 1190, 3204, 1181, 3213, 1189,
                     3215, 1179, 3218, 1193, 3231, 1192, 3228, 1175, 3234, 1192, 3244, 1178, 3238, 1191, 3251, 1194,
                     3225, 1199, 3231, 1211, 3223, 1218, 3227, 1210, 3213, 1201, 3205, 1203, 3225, 1257, 3230, 1249,
                     3231, 1239, 3231, 1257, 3240, 1255, 3233, 1264, 3252, 1264, 3237, 1271, 3229, 1257, 3233, 1282,
                     3251, 1268, 3262, 1268, 3277, 1275, 3270, 1264, 3268, 1256, 3258, 1251, 3263, 1242, 3252, 1232,
                     3238, 1219, 3244, 1212, 3244, 1220, 3250, 1215, 3250, 1223, 3255, 1217, 3255, 1226, 3266, 1222,
                     3275, 1223, 3259, 1230, 3271, 1236, 3289, 1233, 3279, 1239, 3279, 1250, 3296, 1252, 3306, 1255,
                     3287, 1259, 3315, 1281, 3311, 1270, 3326, 1274, 3325, 1291, 3333, 1271, 3323, 1253, 3316, 1233,
                     3308, 1234, 3310, 1215, 3314, 1230, 3323, 1230, 3324, 1243, 3349, 1236, 3335, 1219, 3326, 1211,
                     3334, 1213, 3348, 1207, 3346, 1198, 3358, 1187, 3361, 1175, 3353, 1177, 3342, 1172, 3346, 1159,
                     3333, 1155, 3329, 1147, 3312, 1138, 3309, 1130, 3306, 1121, 3296, 1116, 3310, 1116, 3317, 1126,
                     3333, 1115, 3322, 1128, 3330, 1137, 3341, 1135, 3343, 1144, 3356, 1148, 3354, 1165, 3371, 1160,
                     3380, 1170, 3375, 1179, 3374, 1198, 3359, 1216, 3366, 1231, 3379, 1232, 3372, 1219, 3381, 1228,
                     3383, 1210, 3386, 1220, 3404, 1208, 3399, 1217, 3415, 1228, 3404, 1226, 3386, 1228, 3384, 1239,
                     3392, 1245, 3381, 1237, 3362, 1250, 3371, 1258, 3368, 1280, 3381, 1300, 3391, 1325, 3391, 1333,
                     3403, 1331, 3399, 1320, 3407, 1312, 3404, 1302, 3395, 1300, 3396, 1292, 3394, 1274, 3405, 1267,
                     3402, 1286, 3410, 1286, 3407, 1297, 3419, 1303, 3417, 1311, 3425, 1308, 3422, 1296, 3421, 1273,
                     3434, 1274, 3431, 1289, 3427, 1294, 3435, 1294, 3430, 1303, 3443, 1299, 3445, 1308, 3430, 1307,
                     3431, 1320, 3420, 1315, 3413, 1326, 3425, 1336, 3433, 1338, 3439, 1326, 3449, 1327, 3435, 1338,
                     3437, 1356, 3446, 1355, 3449, 1347, 3445, 1359, 3460, 1373, 3473, 1408, 3490, 1430, 3512, 1430,
                     3526, 1434, 3516, 1430, 3497, 1427, 3487, 1423, 3490, 1409, 3498, 1421, 3506, 1426, 3505, 1414,
                     3514, 1425, 3519, 1417, 3529, 1415, 3512, 1397, 3525, 1400, 3522, 1346, 3507, 1307, 3538, 1272,
                     3530, 1256, 3529, 1265, 3527, 1254, 3521, 1241, 3508, 1239, 3520, 1239, 3487, 1196, 3474, 1166,
                     3443, 1123, 3424, 1056, 3427, 1023, 3433, 1011, 3461, 975, 3422, 956, 3410, 965, 3390, 964, 3395,
                     930, 3441, 860, 3436, 833, 3449, 814, 3428, 807, 3419, 799, 3400, 761, 3384, 746, 3371, 726, 3348,
                     709, 3343, 700, 3330, 679, 3319, 668, 3296, 646, 3276, 611, 3251, 537, 3253, 432, 3261, 387, 3255,
                     379, 3238, 317, 3229, 246, 3211, 256, 3197, 264, 3206, 261, 3207, 252, 3223, 243, 3239, 184, 3217,
                     176, 3214, 186, 3216, 176, 3204, 169, 3194, 149, 3194, 140, 3185, 139, 3194, 137, 3191, 121, 3190,
                     103, 3180, 101, 3185, 74, 3185, 89, 3194, 70, 3195, 61, 3188, 42, 3198, 61, 3188, 91, 3197, 99,
                     3208, 91, 3219, 89, 3206, 84, 3209, 71, 3219, 74, 3216, 83, 3226, 79, 3239, 67, 3223, 69, 3220, 59,
                     3226, 67, 3236, 66, 3236, 55, 3221, 49, 3234, 50, 3236, 42, 3240, 53, 3262, 40, 3268, 32, 3267, 24,
                     3280, 14, 3282, 3, 3285, -18, 3292, -32, 3282, -57, 3276, -53, 3276, -45, 3264, -42, 3255, -43,
                     3267, -47, 3258, -53, 3244, -48, 3235, -52, 3229, -34, 3238, -28, 3254, -20, 3236, -19, 3242, -6,
                     3233, -10, 3229, -18, 3221, -21, 3211, -17, 3214, -9, 3206, -7, 3202, -16, 3201, -25, 3211, -21,
                     3199, -38, 3210, -36, 3215, -28, 3222, -40, 3214, -49, 3212, -59, 3223, -48, 3223, -67, 3213, -66,
                     3214, -75, 3227, -75, 3223, -87, 3232, -75, 3242, -81, 3237, -94, 3244, -74, 3249, -86, 3239, -98,
                     3242, -111, 3231, -105, 3223, -109, 3218, -100, 3212, -108, 3209, -98, 3201, -98, 3198, -112, 3201,
                     -103, 3213, -112, 3220, -122, 3230, -128, 3238, -121, 3250, -118, 3252, -110, 3257, -122, 3261,
                     -110, 3252, -101, 3263, -87, 3290, -117, 3289, -128, 4224, -128, 4224, -128, 3474, -128, 3475,
                     -116, 3486, -120, 3475, -115, 3473, -89, 3458, -49, 3458, -31, 3469, -26, 3476, -53, 3493, -64,
                     3507, -62, 3502, -77, 3504, -95, 3507, -75, 3510, -85, 3509, -67, 3523, -78, 3513, -128, 3509,
                     -119, 3509, -128, 3717, -128, 3705, -60, 3718, -44, 3721, -21, 3735, -16, 3727, -13, 3724, -3,
                     3716, 18, 3714, 38, 3723, 41, 3719, 29, 3727, 30, 3736, 24, 3739, 15, 3754, 13, 3761, -1, 3771, -9,
                     3765, -1, 3763, 10, 3755, 14, 3764, 18, 3739, 25, 3742, 35, 3725, 50, 3735, 54, 3734, 72, 3742, 70,
                     3752, 54, 3760, 51, 3768, 50, 3779, 46, 3764, 53, 3748, 66, 3758, 80, 3768, 73, 3758, 88, 3782, 84,
                     3785, 75, 3794, 67, 3794, 59, 3807, 50, 3815, 56, 3825, 47, 3819, 43, 3819, 25, 3819, 1, 3812, -11,
                     3821, -7, 3833, -17, 3846, -36, 3859, -51, 3854, -41, 3844, -33, 3837, -19, 3823, -5, 3826, 12,
                     3835, 8, 3826, 15, 3823, 26, 3829, 39, 3841, 30, 3841, 22, 3850, 20, 3865, 19, 3842, 32, 3831, 46,
                     3871, 49, 3850, 53, 3840, 53, 3830, 56, 3818, 62, 3827, 67, 3822, 78, 3815, 66, 3807, 66, 3812, 77,
                     3805, 69, 3796, 77, 3799, 88, 3788, 93, 3793, 101, 3787, 94, 3779, 94, 3779, 106, 3768, 106, 3765,
                     116, 3777, 114, 3765, 119, 3752, 134, 3751, 142, 3760, 149, 3745, 148, 3750, 137, 3735, 120, 3733,
                     103, 3724, 99, 3716, 89, 3713, 103, 3706, 91, 3703, 79, 3690, 67, 3681, 69, 3681, 58, 3693, 51,
                     3685, 49, 3684, 41, 3680, 31, 3692, 40, 3674, 6, 3672, 16, 3667, 5, 3658, 5, 3662, 13, 3651, 19,
                     3645, 11, 3643, -1, 3641, -14, 3633, -18, 3634, -9, 3623, -8, 3622, -18, 3632, -24, 3630, -34,
                     3620, -36, 3617, -20, 3614, -28, 3612, -41, 3618, -40, 3618, -55, 3638, -65, 3636, -74, 3598, -35,
                     3602, -16, 3593, -15, 3587, -5, 3576, -6, 3565, 1, 3557, 13, 3554, 48, 3541, 66, 3542, 74, 3536,
                     92, 3526, 90, 3531, 104, 3529, 112, 3525, 122, 3521, 114, 3510, 126, 3509, 169, 3513, 178, 3519,
                     162, 3518, 174, 3518, 191, 3510, 190, 3503, 218, 3506, 231, 3501, 245, 3504, 270, 3511, 284, 3510,
                     265, 3506, 265, 3506, 254, 3516, 260, 3515, 250, 3524, 263, 3534, 268, 3536, 250, 3528, 245, 3518,
                     224, 3521, 211, 3527, 200, 3527, 191, 3541, 170, 3549, 171, 3547, 159, 3539, 162, 3530, 160, 3531,
                     147, 3539, 149, 3539, 138, 3543, 147, 3548, 125, 3542, 117, 3540, 101, 3548, 101, 3549, 81, 3558,
                     94, 3568, 101, 3574, 92, 3563, 79, 3569, 87, 3581, 89, 3570, 75, 3568, 65, 3568, 55, 3573, 69,
                     3582, 80, 3582, 71, 3585, 71, 3585, 60, 3588, 73, 3593, 64, 3591, 73, 3588, 82, 3589, 91, 3601, 86,
                     3602, 72, 3603, 51, 3595, 41, 3586, 42, 3582, 16, 3588, 25, 3590, 38, 3598, 36, 3610, 53, 3610, 42,
                     3618, 39, 3611, 24, 3626, 20, 3625, 11, 3631, 19, 3618, 30, 3621, 38, 3614, 59, 3616, 74, 3609, 85,
                     3612, 93, 3602, 99, 3592, 103, 3577, 110, 3569, 125, 3572, 138, 3573, 160, 3576, 162, 3576, 171,
                     3574, 182, 3570, 193, 3578, 184, 3585, 193, 3594, 199, 3610, 212, 3610, 197, 3603, 199, 3603, 187,
                     3590, 181, 3582, 172, 3594, 169, 3597, 175, 3597, 166, 3601, 176, 3611, 183, 3616, 173, 3610, 164,
                     3621, 173, 3634, 162, 3630, 151, 3619, 161, 3611, 159, 3598, 153, 3587, 160, 3594, 148, 3590, 139,
                     3581, 139, 3583, 119, 3588, 135, 3596, 137, 3597, 128, 3599, 143, 3607, 118, 3605, 147, 3610, 136,
                     3617, 146, 3619, 138, 3627, 127, 3617, 121, 3614, 111, 3635, 120, 3637, 130, 3633, 137, 3649, 137,
                     3646, 124, 3644, 114, 3625, 105, 3623, 91, 3623, 78, 3626, 69, 3630, 42, 3636, 54, 3649, 40, 3655,
                     29, 3656, 45, 3643, 51, 3642, 59, 3633, 62, 3631, 70, 3631, 78, 3646, 71, 3634, 88, 3643, 93, 3642,
                     102, 3655, 101, 3663, 112, 3669, 97, 3654, 96, 3666, 94, 3662, 80, 3672, 81, 3674, 97, 3683, 88,
                     3692, 96, 3682, 98, 3687, 111, 3681, 103, 3672, 112, 3682, 122, 3679, 135, 3690, 141, 3695, 150,
                     3695, 129, 3705, 147, 3715, 161, 3714, 141, 3707, 129, 3715, 126, 3712, 135, 3718, 146, 3720, 136,
                     3729, 140, 3726, 151, 3725, 173, 3726, 159, 3738, 154, 3730, 162, 3733, 178, 3738, 170, 3733, 185,
                     3722, 182, 3711, 176, 3708, 186, 3706, 175, 3689, 178, 3689, 186, 3682, 178, 3679, 168, 3671, 156,
                     3659, 161, 3668, 170, 3669, 186, 3661, 185, 3657, 195, 3658, 206, 3664, 217, 3675, 233, 3675, 209,
                     3673, 199, 3689, 214, 3695, 203, 3699, 216, 3712, 220, 3710, 204, 3714, 215, 3715, 230, 3707, 229,
                     3697, 225, 3689, 223, 3696, 233, 3687, 231, 3696, 245, 3692, 253, 3696, 263, 3712, 281, 3642, 370,
                     3642, 391, 3631, 389, 3633, 400, 3625, 383, 3622, 397, 3613, 397, 3600, 392, 3601, 383, 3589, 367,
                     3599, 394, 3606, 411, 3627, 407, 3624, 415, 3620, 424, 3609, 432, 3619, 429, 3624, 437, 3616, 436,
                     3616, 446, 3601, 455, 3596, 473, 3592, 462, 3583, 457, 3585, 448, 3574, 458, 3561, 466, 3570, 472,
                     3585, 475, 3599, 492, 3605, 507, 3603, 519, 3614, 517, 3617, 509, 3609, 506, 3607, 497, 3604, 483,
                     3612, 479, 3610, 468, 3610, 458, 3618, 465, 3615, 487, 3622, 489, 3622, 503, 3625, 513, 3633, 513,
                     3634, 525, 3643, 529, 3641, 517, 3642, 506, 3632, 506, 3642, 498, 3640, 491, 3632, 491, 3628, 482,
                     3637, 484, 3645, 475, 3637, 470, 3638, 461, 3646, 463, 3635, 427, 3641, 435, 3654, 431, 3652, 420,
                     3658, 412, 3669, 419, 3659, 417, 3661, 425, 3656, 435, 3645, 439, 3653, 451, 3650, 473, 3660, 475,
                     3647, 484, 3648, 513, 3652, 510, 3652, 489, 3660, 485, 3657, 493, 3658, 507, 3653, 516, 3661, 512,
                     3671, 507, 3682, 507, 3681, 498, 3677, 485, 3687, 483, 3680, 473, 3668, 473, 3670, 464, 3667, 454,
                     3674, 449, 3684, 449, 3684, 436, 3692, 436, 3686, 451, 3675, 456, 3678, 464, 3675, 466, 3687, 466,
                     3687, 474, 3698, 478, 3702, 474, 3702, 464, 3706, 465, 3706, 457, 3710, 458, 3710, 431, 3713, 446,
                     3706, 475, 3700, 492, 3708, 487, 3719, 488, 3721, 478, 3723, 487, 3732, 484, 3736, 475, 3745, 469,
                     3744, 461, 3736, 451, 3737, 436, 3740, 446, 3747, 462, 3759, 449, 3761, 459, 3770, 463, 3786, 462,
                     3768, 467, 3757, 463, 3747, 485, 3755, 488, 3757, 499, 3752, 491, 3743, 514, 3738, 496, 3729, 499,
                     3718, 504, 3706, 504, 3694, 514, 3709, 525, 3705, 535, 3713, 536, 3716, 545, 3731, 543, 3746, 546,
                     3740, 537, 3748, 542, 3747, 534, 3758, 542, 3762, 531, 3761, 539, 3771, 538, 3780, 538, 3781, 530,
                     3787, 540, 3792, 536, 3792, 525, 3808, 524, 3820, 512, 3810, 527, 3794, 529, 3795, 540, 3796, 548,
                     3806, 544, 3817, 551, 3826, 549, 3816, 555, 3801, 547, 3798, 568, 3793, 558, 3792, 542, 3775, 547,
                     3779, 561, 3772, 541, 3764, 548, 3751, 546, 3747, 557, 3760, 559, 3749, 571, 3749, 579, 3754, 588,
                     3765, 589, 3777, 598, 3768, 595, 3750, 594, 3747, 586, 3737, 591, 3746, 582, 3746, 563, 3742, 551,
                     3724, 557, 3727, 565, 3721, 555, 3709, 559, 3707, 546, 3697, 548, 3689, 529, 3681, 528, 3685, 543,
                     3695, 554, 3692, 565, 3698, 577, 3683, 579, 3681, 588, 3677, 569, 3674, 556, 3666, 553, 3659, 562,
                     3660, 592, 3649, 570, 3652, 561, 3644, 559, 3623, 595, 3633, 616, 3625, 618, 3619, 607, 3606, 612,
                     3593, 631, 3584, 658, 3592, 673, 3579, 669, 3578, 658, 3570, 657, 3560, 639, 3572, 653, 3580, 650,
                     3578, 642, 3581, 629, 3582, 640, 3595, 611, 3585, 612, 3583, 604, 3589, 596, 3568, 600, 3553, 608,
                     3553, 617, 3544, 607, 3527, 604, 3535, 618, 3532, 637, 3521, 626, 3520, 636, 3524, 652, 3538, 675,
                     3549, 683, 3551, 694, 3565, 709, 3580, 741, 3594, 757, 3599, 778, 3594, 803, 3601, 820, 3609, 833,
                     3630, 848, 3638, 850, 3649, 873, 3661, 887, 3674, 878, 3666, 852, 3668, 829, 3676, 823, 3667, 805,
                     3672, 797, 3681, 798, 3690, 807, 3695, 827, 3693, 838, 3688, 853, 3699, 851, 3709, 842, 3720, 856,
                     3739, 865, 3757, 897, 3755, 905, 3762, 914, 3774, 932, 3761, 933, 3755, 925, 3766, 944, 3775, 945,
                     3793, 954, 3814, 957, 3813, 970, 3802, 973, 3802, 988, 3788, 1002, 3788, 1025, 3766, 1025, 3789,
                     1026, 3839, 1025, 3789, 1025, 3791, 1015, 3804, 1008, 3826, 1009, 3814, 998, 3815, 970, 3827, 976,
                     3834, 964, 3842, 977, 3851, 980, 3837, 988, 3844, 998, 3859, 988, 3864, 999, 3861, 1008, 3872,
                     1009, 3887, 1009, 3880, 1024, 3888, 1023, 3891, 1034, 3877, 1045, 3868, 1043, 3859, 1052, 3851,
                     1046, 3860, 1059, 3896, 1062, 3902, 1080, 3921, 1107, 3956, 1127, 3952, 1100, 3941, 1079, 3940,
                     1068, 3949, 1033, 3948, 1025, 3958, 1019, 3965, 1008, 3960, 995, 3932, 966, 3917, 964, 3929, 957,
                     3943, 933, 3979, 912, 3987, 877, 3995, 871, 3988, 862, 4002, 835, 4013, 843, 4043, 850, 4061, 902,
                     4059, 919, 4058, 928, 4038, 944, 3979, 955, 3992, 967, 4029, 1023, 4029, 1023, 4029, 1037, 4059,
                     1062, 4065, 1076, 4064, 1087, 4060, 1076, 4049, 1096, 4079, 1089, 4090, 1072, 4097, 1072, 4139,
                     1072, 4155, 1105, 4174, 1105, 4166, 1086, 4176, 1075, 4174, 1065, 4185, 1057, 4193, 1052, 4195,
                     1064, 4191, 1078, 4208, 1098, 4208, 1106, 4222, 1110, 4224, 1109, 4224, 1144, 4202, 1158, 4177,
                     1161, 4182, 1181, 4169, 1152, 4140, 1163, 4117, 1177, 4134, 1177, 4126, 1181, 4124, 1189, 4115,
                     1194, 4115, 1178, 4096, 1179, 4075, 1201, 4081, 1215, 4086, 1216, 4086, 1205, 4087, 1214, 4095,
                     1216, 4109, 1227, 4102, 1242, 4100, 1231, 4096, 1234, 4096, 1244, 4103, 1254, 4115, 1249, 4127,
                     1259, 4131, 1250, 4133, 1258, 4140, 1245, 4138, 1256, 4141, 1275, 4150, 1271, 4142, 1271, 4159,
                     1255, 4169, 1255, 4168, 1246, 4177, 1245, 4180, 1259, 4190, 1271, 4182, 1272, 4196, 1281, 4192,
                     1267, 4209, 1270, 4218, 1267, 4221, 1249, 4214, 1230, 4215, 1215, 4221, 1223, 4219, 1231, 4224,
                     1243, 4224, 1257, 4224, 1262, 4224, 1345, 4224, 1339, 4224, 1328, 4215, 1335, 4213, 1346, 4203,
                     1355, 4213, 1357, 4215, 1369, 4224, 1363, 4215, 1377, 4208, 1387, 4217, 1401, 4224, 1403, 4224,
                     1520, 4219, 1535, 4221, 1544, 4217, 1553, 4209, 1549, 4215, 1558, 4206, 1559, 4207, 1580, 4199,
                     1593, 4205, 1605, 4215, 1604, 4223, 1595, 4221, 1611, 4212, 1608, 4211, 1618, 4206, 1626, 4214,
                     1625, 4219, 1637, 4214, 1648, 4224, 1645, 4224, 1640, 4224, 2108, 4220, 2125, 4224, 2125, 4224,
                     2143, 4205, 2141, 4180, 2159, 4188, 2155, 4195, 2165, 4207, 2164, 4196, 2172, 4201, 2182, 4187,
                     2168, 4170, 2169, 4171, 2181, 4163, 2189, 4173, 2188, 4163, 2194, 4164, 2202, 4173, 2196, 4179,
                     2205, 4186, 2196, 4185, 2205, 4174, 2208, 4176, 2229, 4192, 2223, 4199, 2211, 4210, 2218, 4212,
                     2210, 4223, 2214, 4224, 2207, 4224, 2216, 4217, 2225, 4221, 2233, 4215, 2224, 4203, 2227, 4199,
                     2238, 4209, 2248, 4197, 2242, 4185, 2240, 4186, 2254, 4198, 2276, 4187, 2260, 4178, 2259, 4161,
                     2258, 4153, 2249, 4150, 2238, 4150, 2228, 4136, 2231, 4144, 2218, 4114, 2274, 4123, 2272, 4133,
                     2270, 4117, 2280, 4139, 2273, 4152, 2274, 4140, 2276, 4133, 2284, 4141, 2288, 4147, 2303, 4157,
                     2311, 4171, 2308, 4163, 2310, 4158, 2319, 4144, 2315, 4135, 2305, 4125, 2299, 4108, 2303, 4097,
                     2318, 4091, 2343, 4096, 2347, 4096, 2339, 4112, 2344, 4110, 2332, 4119, 2332, 4121, 2347, 4131,
                     2344, 4146, 2338, 4155, 2337, 4164, 2350, 4180, 2355, 4195, 2352, 4200, 2342, 4201, 2354, 4213,
                     2352, 4224, 2348, 4224, 2356, 4207, 2361, 4184, 2358, 4176, 2367, 4162, 2364, 4155, 2354, 4141,
                     2357, 4119, 2361, 4115, 2355, 4106, 2355, 4101, 2364, 4105, 2372, 4108, 2386, 4096, 2372, 4091,
                     2388, 4078, 2409, 4067, 2446, 4059, 2493, 4073, 2495, 4074, 2478, 4073, 2490, 4087, 2492, 4084,
                     2484, 4089, 2481, 4097, 2481, 4099, 2473, 4088, 2474, 4092, 2464, 4103, 2465, 4102, 2473, 4118,
                     2470, 4118, 2459, 4129, 2458, 4129, 2449, 4121, 2447, 4126, 2439, 4135, 2447, 4143, 2440, 4142,
                     2426, 4148, 2416, 4156, 2414, 4159, 2406, 4161, 2417, 4153, 2419, 4144, 2434, 4154, 2440, 4152,
                     2449, 4163, 2459, 4171, 2453, 4166, 2461, 4153, 2458, 4136, 2458, 4121, 2480, 4141, 2472, 4157,
                     2483, 4168, 2487, 4160, 2482, 4149, 2480, 4140, 2480, 4128, 2487, 4112, 2483, 4102, 2487, 4097,
                     2499, 4098, 2510, 4108, 2514, 4117, 2522, 4140, 2526, 4126, 2524, 4114, 2523, 4100, 2524, 4091,
                     2519, 4084, 2528, 4093, 2511, 4089, 2501, 4079, 2509, 4065, 2508, 4057, 2516, 4050, 2536, 4067,
                     2544, 4057, 2546, 4057, 2558, 4050, 2538, 4037, 2561, 4029, 2589, 4033, 2579, 4030, 2604, 4034,
                     2629, 4035, 2614, 4034, 2601, 4038, 2593, 4043, 2610, 4048, 2598, 4063, 2585, 4076, 2582, 4080,
                     2573, 4089, 2570, 4097, 2562, 4095, 2571, 4075, 2586, 4084, 2597, 4097, 2592, 4108, 2591, 4095,
                     2596, 4103, 2601, 4095, 2605, 4087, 2606, 4066, 2597, 4063, 2606, 4073, 2606, 4048, 2618, 4052,
                     2632, 4052, 2642, 4064, 2646, 4082, 2654, 4091, 2645, 4084, 2654, 4097, 2656, 4094, 2667, 4085,
                     2664, 4086, 2672, 4080, 2656, 4068, 2654, 4060, 2654, 4042, 2652, 4053, 2661, 4045, 2660, 4035,
                     2665, 4025, 2666, 4026, 2684, 4032, 2697, 4046, 2699, 4037, 2714, 4039, 2702, 4031, 2709, 4027,
                     2691, 3983, 2765, 3974, 2811, 3974, 2820, 3977, 2809, 3985, 2796, 3995, 2794, 3998, 2785, 4007,
                     2786, 4004, 2776, 4012, 2775, 4015, 2755, 4022, 2763, 4038, 2761, 4020, 2771, 4035, 2784, 4044,
                     2783, 4034, 2789, 4024, 2793, 4024, 2798, 4013, 2798, 4017, 2810, 4013, 2802, 4001, 2803, 4002,
                     2818, 4013, 2823, 4003, 2819, 3991, 2818, 3982, 2835, 3983, 2846, 3993, 2848, 4005, 2853, 4017,
                     2855, 4028, 2846, 4019, 2853, 4027, 2861, 4010, 2854, 4000, 2854, 3992, 2861, 3992, 2851, 3973,
                     2866, 3968, 2877, 3984, 2880, 3967, 2885, 3970, 2902, 3983, 2931, 3987, 2920, 3988, 2931, 4002,
                     2936, 4010, 2917, 4008, 2903, 4016, 2893, 4021, 2901, 4012, 2913, 4026, 2916, 4014, 2921, 4015,
                     2934, 4032, 2937, 4018, 2934, 4014, 2944, 4024, 2948, 4015, 2950, 4006, 2943, 3992, 2946, 3986,
                     2988, 3992, 3004, 4017, 3037, 4023, 3053, 4022, 3063, 4031, 3065, 4036, 3073, 4050, 3135, 4050,
                     3151, 4091, 3119, 4083, 3115, 4076, 3096, 4087, 3101, 4086, 3072, 4087, 3061, 4087, 3046, 4094,
                     3022, 4092, 3012, 4091, 3001, 4097, 2989, 4097, 3013, 4098, 2945, 4101, 2937, 4097, 2920, 4105,
                     2913, 4113, 2856, 4122, 2844, 4112, 2840, 4123, 2834, 4124, 2817, 4129, 2791, 4136, 2775, 4140,
                     2760, 4130, 2754, 4145, 2754, 4154, 2742, 4150, 2733, 4139, 2720, 4154, 2722, 4159, 2707, 4183,
                     2662, 4182, 2654, 4183, 2640, 4189, 2644, 4189, 2653, 4197, 2632, 4209, 2634, 4205, 2624, 4213,
                     2607, 4203, 2605, 4209, 2589, 4211, 2600, 4219, 2599, 4224, 2592, 4224, 2574, 4223, 2566, 4224,
                     2562, 4224, 2553, 4224, 2552, 4224, -128, 4224, 4224, 4205, 4224, 4183, 4096, 4158, 4018, 4122,
                     3935, 4097, 3854, 4092, 3841, 4075, 3785, 4050, 3675, 4045, 3686, 4047, 3676, 4031, 3585, 4015,
                     3513, 3993, 3494, 3963, 3488, 3945, 3491, 3919, 3515, 3880, 3525, 3873, 3533, 3887, 3539, 3897,
                     3536, 3924, 3532, 3923, 3524, 3925, 3533, 3936, 3526, 3950, 3529, 3962, 3536, 3976, 3555, 3981,
                     3567, 4002, 3574, 4018, 3572, 4003, 3575, 4018, 3580, 4022, 3593, 4014, 3591, 4009, 3579, 3992,
                     3572, 3992, 3585, 3993, 3598, 4002, 3596, 4007, 3594, 4007, 3603, 4010, 3613, 4027, 3623, 4012,
                     3619, 4004, 3619, 4005, 3609, 3995, 3606, 3986, 3604, 3995, 3609, 3990, 3617, 3998, 3617, 3999,
                     3627, 3987, 3633, 3991, 3622, 3978, 3621, 3985, 3610, 3981, 3600, 3981, 3590, 3986, 3598, 3986,
                     3585, 3976, 3587, 3984, 3581, 3983, 3571, 3975, 3572, 3967, 3566, 3948, 3558, 3955, 3583, 3946,
                     3559, 3936, 3547, 3882, 3539, 3879, 3548, 3887, 3553, 3893, 3543, 3891, 3556, 3899, 3562, 3898,
                     3554, 3907, 3558, 3909, 3544, 3913, 3557, 3915, 3566, 3907, 3567, 3905, 3577, 3916, 3574, 3911,
                     3584, 3914, 3592, 3916, 3583, 3920, 3598, 3909, 3596, 3901, 3596, 3907, 3604, 3913, 3612, 3908,
                     3625, 3917, 3622, 3923, 3631, 3914, 3628, 3919, 3647, 3922, 3656, 3917, 3666, 3922, 3655, 3913,
                     3650, 3916, 3641, 3915, 3632, 3906, 3639, 3907, 3647, 3898, 3647, 3908, 3632, 3899, 3631, 3905,
                     3623, 3903, 3615, 3895, 3624, 3897, 3632, 3894, 3622, 3883, 3622, 3891, 3625, 3888, 3614, 3898,
                     3617, 3901, 3607, 3890, 3610, 3891, 3600, 3892, 3588, 3903, 3590, 3893, 3583, 3890, 3574, 3877,
                     3572, 3880, 3581, 3872, 3589, 3869, 3574, 3869, 3563, 3858, 3561, 3860, 3573, 3851, 3572, 3851,
                     3583, 3847, 3591, 3855, 3588, 3854, 3601, 3865, 3597, 3861, 3605, 3869, 3605, 3858, 3605, 3850,
                     3599, 3841, 3611, 3842, 3622, 3852, 3623, 3843, 3624, 3843, 3634, 3840, 3625, 3823, 3628, 3821,
                     3638, 3813, 3642, 3822, 3625, 3836, 3616, 3828, 3615, 3830, 3606, 3840, 3605, 3847, 3596, 3839,
                     3591, 3849, 3584, 3837, 3581, 3825, 3591, 3831, 3583, 3830, 3571, 3839, 3577, 3832, 3566, 3844,
                     3568, 3841, 3558, 3851, 3557, 3851, 3542, 3842, 3535, 3863, 3543, 3865, 3534, 3802, 3504, 3749,
                     3491, 3749, 3507, 3764, 3505, 3750, 3513, 3767, 3518, 3742, 3522, 3734, 3526, 3739, 3508, 3729,
                     3507, 3745, 3506, 3745, 3489, 3684, 3476, 3607, 3424, 3585, 3422, 3573, 3420, 3569, 3428, 3583,
                     3430, 3583, 3430, 3608, 3430, 3619, 3435, 3609, 3433, 3607, 3452, 3588, 3459, 3587, 3468, 3578,
                     3464, 3568, 3455, 3567, 3445, 3555, 3447, 3546, 3446, 3536, 3439, 3523, 3438, 3528, 3447, 3520,
                     3446, 3528, 3448, 3520, 3453, 3526, 3463, 3518, 3472, 3531, 3476, 3520, 3478, 3518, 3482, 3526,
                     3482, 3519, 3486, 3532, 3486, 3519, 3488, 3527, 3514, 3530, 3540, 3541, 3520, 3550, 3529, 3560,
                     3533, 3562, 3524, 3570, 3520, 3565, 3530, 3573, 3524, 3571, 3534, 3583, 3538, 3583, 3536, 3583,
                     3526, 3594, 3523, 3592, 3532, 3586, 3545, 3585, 3554, 3584, 3563, 3590, 3551, 3591, 3561, 3600,
                     3565, 3605, 3551, 3608, 3543, 3621, 3543, 3629, 3551, 3613, 3549, 3619, 3559, 3631, 3564, 3618,
                     3563, 3614, 3553, 3611, 3563, 3606, 3576, 3613, 3584, 3608, 3593, 3615, 3604, 3628, 3611, 3605,
                     3600, 3607, 3586, 3601, 3572, 3591, 3575, 3593, 3567, 3583, 3566, 3577, 3577, 3580, 3564, 3567,
                     3568, 3576, 3561, 3573, 3553, 3566, 3540, 3556, 3544, 3558, 3553, 3552, 3539, 3543, 3573, 3534,
                     3578, 3522, 3584, 3530, 3585, 3522, 3589, 3527, 3597, 3542, 3604, 3542, 3612, 3550, 3612, 3557,
                     3622, 3568, 3634, 3566, 3623, 3569, 3627, 3577, 3627, 3575, 3638, 3585, 3650, 3605, 3655, 3626,
                     3651, 3649, 3657, 3658, 3656, 3655, 3648, 3661, 3657, 3671, 3657, 3674, 3649, 3669, 3640, 3669,
                     3628, 3679, 3631, 3679, 3643, 3684, 3651, 3695, 3648, 3679, 3653, 3686, 3663, 3694, 3658, 3693,
                     3670, 3703, 3667, 3706, 3659, 3704, 3668, 3718, 3655, 3712, 3676, 3722, 3674, 3722, 3681, 3714,
                     3681, 3699, 3671, 3696, 3683, 3692, 3694, 3691, 3685, 3693, 3673, 3682, 3668, 3679, 3679, 3681,
                     3663, 3671, 3670, 3675, 3662, 3666, 3662, 3657, 3664, 3671, 3676, 3672, 3687, 3661, 3687, 3652,
                     3702, 3651, 3692, 3664, 3682, 3654, 3671, 3647, 3663, 3636, 3663, 3631, 3678, 3633, 3662, 3617,
                     3660, 3610, 3669, 3605, 3659, 3596, 3657, 3583, 3656, 3578, 3672, 3584, 3680, 3589, 3689, 3585,
                     3691, 3594, 3691, 3585, 3692, 3584, 3694, 3584, 3703, 3587, 3713, 3600, 3711, 3589, 3713, 3583,
                     3719, 3583, 3739, 3566, 3748, 3566, 3759, 3558, 3766, 3574, 3769, 3585, 3759, 3576, 3770, 3578,
                     3778, 3578, 3788, 3573, 3802, 3583, 3804, 3575, 3804, 3579, 3812, 3574, 3823, 3572, 3835, 3585,
                     3846, 3605, 3855, 3614, 3851, 3637, 3864, 3650, 3861, 3660, 3867, 3651, 3869, 3642, 3864, 3633,
                     3865, 3624, 3870, 3615, 3855, 3603, 3857, 3589, 3857, 3579, 3850, 3571, 3846, 3567, 3837, 3571,
                     3829, 3573, 3811, 3563, 3805, 3550, 3802, 3560, 3798, 3564, 3784, 3561, 3797, 3574, 3775, 3554,
                     3769, 3547, 3778, 3553, 3769, 3543, 3759, 3534, 3759, 3522, 3759, 3533, 3757, 3541, 3757, 3554,
                     3764, 3560, 3745, 3575, 3738, 3566, 3733, 3543, 3711, 3568, 3731, 3579, 3726, 3580, 3718, 3579,
                     3708, 3567, 3708, 3571, 3700, 3580, 3691, 3573, 3672, 3574, 3655, 3564, 3655, 3563, 3640, 3548,
                     3640, 3537, 3646, 3537, 3659, 3537, 3648, 3529, 3648, 3540, 3640, 3551, 3634, 3543, 3628, 3522,
                     3626, 3507, 3629, 3508, 3641, 3496, 3636, 3493, 3644, 3496, 3653, 3490, 3645, 3491, 3654, 3482,
                     3653, 3486, 3667, 3474, 3666, 3474, 3676, 3485, 3689, 3474, 3681, 3472, 3668, 3463, 3666, 3460,
                     3677, 3456, 3662, 3441, 3668, 3438, 3682, 3428, 3684, 3424, 3692, 3418, 3705, 3423, 3717, 3416,
                     3725, 3416, 3702, 3420, 3692, 3428, 3671, 3438, 3669, 3443, 3660, 3439, 3649, 3431, 3650, 3439,
                     3646, 3441, 3636, 3446, 3656, 3465, 3656, 3473, 3652, 3474, 3644, 3483, 3633, 3475, 3630, 3472,
                     3622, 3465, 3630, 3461, 3621, 3472, 3619, 3468, 3608, 3474, 3620, 3484, 3623, 3507, 3621, 3506,
                     3612, 3514, 3608, 3505, 3611, 3490, 3607, 3500, 3606, 3493, 3583, 3492, 3575, 3472, 3576, 3463,
                     3574, 3481, 3569, 3491, 3567, 3508, 3577, 3511, 3559, 3496, 3556, 3487, 3503, 3447, 3502, 3440,
                     3554, 3411, 3553, 3385, 3540, 3361, 3536, 3349, 3543, 3344, 3560, 3343, 3575, 3329, 3577, 3329,
                     3578, 3320, 3578, 3312, 3580, 3304, 3591, 3317, 3587, 3309, 3591, 3312, 3599, 3307, 3619, 3304,
                     3630, 3300, 3621, 3307, 3617, 3307, 3608, 3300, 3596, 3301, 3587, 3293, 3581, 3274, 3583, 3283,
                     3583, 3290, 3595, 3278, 3605, 3264, 3607, 3268, 3617, 3259, 3627, 3246, 3628, 3254, 3637, 3267,
                     3635, 3271, 3644, 3263, 3643, 3253, 3644, 3230, 3654, 3226, 3668, 3216, 3667, 3212, 3671, 3197,
                     3671, 3206, 3694, 3203, 3703, 3193, 3709, 3192, 3725, 3196, 3738, 3187, 3749, 3192, 3764, 3208,
                     3762, 3210, 3775, 3197, 3781, 3186, 3780, 3184, 3788, 3185, 3780, 3199, 3779, 3209, 3773, 3207,
                     3763, 3190, 3765, 3184, 3749, 3184, 3729, 3190, 3719, 3182, 3710, 3195, 3699, 3185, 3690, 3181,
                     3672, 3188, 3658, 3204, 3659, 3210, 3649, 3217, 3637, 3231, 3638, 3240, 3610, 3234, 3601, 3253,
                     3597, 3257, 3586, 3262, 3565, 3272, 3560, 3287, 3563, 3295, 3557, 3306, 3521, 3292, 3508, 3289,
                     3516, 3280, 3520, 3274, 3533, 3260, 3531, 3248, 3540, 3236, 3553, 3229, 3565, 3219, 3564, 3216,
                     3574, 3201, 3577, 3192, 3578, 3202, 3576, 3215, 3573, 3218, 3562, 3227, 3564, 3242, 3541, 3236,
                     3518, 3228, 3519, 3237, 3517, 3241, 3532, 3252, 3524, 3250, 3513, 3260, 3519, 3274, 3520, 3263,
                     3509, 3271, 3507, 3280, 3507, 3278, 3478, 3270, 3458, 3261, 3455, 3272, 3458, 3280, 3462, 3284,
                     3471, 3298, 3477, 3294, 3456, 3297, 3444, 3286, 3430, 3257, 3423, 3241, 3406, 3239, 3394, 3220,
                     3388, 3201, 3366, 3183, 3358, 3175, 3364, 3184, 3374, 3175, 3367, 3149, 3375, 3134, 3374, 3121,
                     3376, 3113, 3380, 3098, 3378, 3105, 3388, 3100, 3405, 3108, 3409, 3107, 3418, 3098, 3405, 3100,
                     3397, 3089, 3395, 3101, 3394, 3095, 3375, 3105, 3369, 3115, 3348, 3123, 3357, 3134, 3357, 3137,
                     3366, 3160, 3369, 3158, 3357, 3167, 3337, 3164, 3324, 3151, 3311, 3117, 3300, 3073, 3300, 3058,
                     3297, 3046, 3288, 3030, 3260, 3031, 3236, 3049, 3183, 3048, 3164, 3037, 3143, 3038, 3124, 3034,
                     3109, 3026, 3107, 3030, 3089, 3026, 3072, 3016, 3062, 3013, 3047, 3024, 3051, 3032, 3048, 3032,
                     3056, 3038, 3046, 3029, 3028, 3017, 3020, 3006, 3004, 2998, 3016, 2993, 3040, 2982, 3053, 2991,
                     3061, 2981, 3054, 2975, 3071, 2966, 3091, 2970, 3100, 2973, 3109, 2981, 3120, 2973, 3133, 2962,
                     3130, 2955, 3128, 2967, 3128, 2976, 3119, 2968, 3110, 2969, 3102, 2967, 3094, 2941, 3099, 2925,
                     3096, 2916, 3089, 2905, 3073, 2894, 3056, 2866, 3042, 2862, 3029, 2847, 3019, 2834, 3024, 2836,
                     3038, 2829, 3047, 2813, 3051, 2803, 3052, 2794, 3061, 2776, 3065, 2778, 3061, 2769, 3061, 2794,
                     3053, 2803, 3040, 2814, 3045, 2822, 3037, 2824, 3024, 2832, 3014, 2838, 2988, 2812, 2990, 2745,
                     2984, 2713, 3000, 2693, 3001, 2656, 2970, 2639, 2961, 2623, 2943, 2613, 2942, 2582, 2927, 2571,
                     2929, 2565, 2941, 2553, 2936, 2539, 2944, 2529, 2945, 2538, 2938, 2550, 2923, 2556, 2923, 2564,
                     2923, 2567, 2895, 2560, 2885, 2559, 2868, 2549, 2856, 2547, 2842, 2551, 2832, 2542, 2828, 2558,
                     2826, 2538, 2811, 2529, 2811, 2532, 2822, 2523, 2822, 2496, 2840, 2472, 2883, 2454, 2888, 2452,
                     2896, 2461, 2901, 2451, 2897, 2451, 2885, 2433, 2868, 2423, 2869, 2419, 2844, 2413, 2802, 2398,
                     2818, 2383, 2818, 2375, 2824, 2356, 2820, 2346, 2822, 2331, 2817, 2325, 2826, 2309, 2833, 2309,
                     2840, 2309, 2832, 2315, 2821, 2288, 2841, 2266, 2843, 2255, 2836, 2250, 2809, 2238, 2810, 2224,
                     2792, 2221, 2813, 2191, 2823, 2170, 2839, 2182, 2825, 2163, 2809, 2155, 2799, 2150, 2786, 2142,
                     2794, 2133, 2801, 2121, 2797, 2119, 2783, 2121, 2769, 2143, 2760, 2155, 2743, 2156, 2733, 2146,
                     2721, 2130, 2721, 2105, 2709, 2096, 2695, 2097, 2680, 2115, 2648, 2114, 2621, 2119, 2643, 2103,
                     2682, 2102, 2693, 2112, 2709, 2149, 2716, 2168, 2738, 2165, 2748, 2173, 2759, 2164, 2751, 2165,
                     2764, 2167, 2778, 2177, 2781, 2190, 2775, 2204, 2774, 2222, 2772, 2251, 2770, 2275, 2782, 2285,
                     2773, 2275, 2783, 2278, 2791, 2313, 2799, 2350, 2796, 2339, 2793, 2343, 2778, 2334, 2780, 2338,
                     2772, 2347, 2793, 2362, 2799, 2371, 2794, 2389, 2783, 2405, 2786, 2423, 2781, 2435, 2771, 2425,
                     2773, 2447, 2765, 2442, 2775, 2433, 2779, 2440, 2792, 2441, 2805, 2432, 2851, 2441, 2866, 2454,
                     2851, 2473, 2839, 2496, 2816, 2487, 2811, 2475, 2823, 2464, 2822, 2455, 2821, 2475, 2819, 2485,
                     2810, 2497, 2814, 2514, 2807, 2527, 2793, 2540, 2804, 2566, 2808, 2563, 2818, 2569, 2826, 2571,
                     2859, 2608, 2909, 2634, 2931, 2651, 2930, 2670, 2938, 2668, 2928, 2674, 2920, 2684, 2922, 2698,
                     2917, 2697, 2908, 2682, 2898, 2699, 2907, 2715, 2903, 2725, 2893, 2724, 2884, 2715, 2876, 2716,
                     2861, 2706, 2839, 2698, 2834, 2702, 2825, 2700, 2840, 2710, 2849, 2718, 2853, 2715, 2835, 2728,
                     2829, 2726, 2817, 2715, 2810, 2709, 2795, 2725, 2785, 2727, 2750, 2731, 2736, 2722, 2729, 2706,
                     2728, 2721, 2728, 2722, 2717, 2712, 2713, 2722, 2716, 2731, 2700, 2726, 2691, 2708, 2707, 2696,
                     2710, 2689, 2725, 2679, 2729, 2676, 2695, 2693, 2682, 2685, 2680, 2665, 2662, 2668, 2653, 2685,
                     2646, 2686, 2625, 2680, 2638, 2669, 2644, 2653, 2636, 2653, 2652, 2649, 2660, 2635, 2666, 2627,
                     2666, 2626, 2651, 2627, 2643, 2631, 2645, 2631, 2662, 2646, 2654, 2652, 2634, 2672, 2640, 2677,
                     2627, 2688, 2623, 2689, 2642, 2686, 2650, 2678, 2655, 2670, 2654, 2687, 2669, 2695, 2658, 2691,
                     2667, 2702, 2677, 2694, 2694, 2682, 2699, 2688, 2707, 2696, 2701, 2705, 2701, 2716, 2689, 2728,
                     2687, 2732, 2695, 2735, 2704, 2745, 2693, 2724, 2724, 2736, 2740, 2744, 2740, 2743, 2732, 2746,
                     2745, 2753, 2732, 2753, 2740, 2773, 2748, 2771, 2740, 2778, 2751, 2792, 2742, 2782, 2746, 2782,
                     2757, 2782, 2767, 2768, 2768, 2765, 2783, 2761, 2791, 2766, 2791, 2766, 2783, 2759, 2795, 2760,
                     2805, 2748, 2798, 2754, 2786, 2740, 2784, 2748, 2798, 2733, 2806, 2746, 2821, 2758, 2826, 2765,
                     2812, 2763, 2825, 2760, 2839, 2738, 2845, 2727, 2840, 2728, 2849, 2739, 2849, 2743, 2861, 2759,
                     2855, 2764, 2842, 2772, 2843, 2783, 2856, 2774, 2881, 2753, 2881, 2729, 2871, 2733, 2882, 2744,
                     2893, 2743, 2902, 2732, 2908, 2740, 2922, 2768, 2925, 2807, 2919, 2823, 2928, 2848, 2940, 2864,
                     2973, 2864, 2959, 2873, 2954, 2881, 2943, 2900, 2942, 2891, 2941, 2904, 2939, 2874, 2956, 2873,
                     2967, 2884, 2967, 2895, 2970, 2938, 2977, 2982, 2968, 2993, 2960, 2984, 2966, 2969, 2964, 2970,
                     2953, 2973, 2943, 2985, 2947, 2981, 2957, 2993, 2949, 3044, 2957, 3061, 2963, 3071, 2970, 3074,
                     2958, 3084, 2960, 3075, 2973, 3098, 3002, 3114, 3055, 3123, 3051, 3118, 3030, 3121, 3019, 3119,
                     3031, 3126, 3040, 3139, 3033, 3153, 3035, 3145, 3033, 3139, 3041, 3130, 3047, 3139, 3054, 3128,
                     3051, 3118, 3060, 3116, 3071, 3116, 3071},
    std::vector<int>{4016, 1878, 4016, 1864, 4029, 1859, 4024, 1850, 4008, 1839, 4006, 1863, 4016, 1878, 4016, 1878},
    std::vector<int>{3315, 1339, 3327, 1332, 3331, 1324, 3323, 1329, 3311, 1313, 3325, 1327, 3321, 1308, 3312, 1308,
                     3290, 1293, 3305, 1315, 3315, 1339, 3315, 1339},
    std::vector<int>{4136, 3071, 4136, 3071, 4136, 3080, 4139, 3072, 4139, 3057, 4139, 3036, 4143, 3020, 4137, 3036,
                     4136, 3071, 4136, 3071},
    std::vector<int>{4218, 3073, 4212, 3077, 4203, 3078, 4206, 3087, 4188, 3104, 4183, 3114, 4171, 3114, 4172, 3122,
                     4164, 3122, 4143, 3131, 4125, 3156, 4117, 3157, 4128, 3161, 4159, 3147, 4223, 3071, 4224, 3071,
                     4224, 3063, 4218, 3073, 4218, 3073},
    std::vector<int>{3912, 3542, 3924, 3541, 3934, 3536, 3942, 3535, 3955, 3536, 3939, 3532, 3949, 3533, 3937, 3527,
                     3929, 3534, 3900, 3540, 3912, 3542, 3912, 3542},
    std::vector<int>{4050, 3172, 4049, 3161, 4044, 3170, 4047, 3190, 4039, 3183, 4044, 3171, 4033, 3187, 4034, 3197,
                     4043, 3210, 4063, 3214, 4085, 3209, 4092, 3193, 4090, 3179, 4068, 3166, 4068, 3174, 4080, 3181,
                     4081, 3192, 4077, 3205, 4064, 3206, 4051, 3200, 4050, 3172, 4050, 3172},
    std::vector<int>{4151, 2998, 4158, 2977, 4155, 2967, 4159, 2946, 4150, 2976, 4147, 2988, 4151, 2985, 4151, 2998,
                     4151, 2998},
    std::vector<int>{2920, 3005, 2935, 2994, 2914, 2986, 2896, 2981, 2884, 2974, 2864, 2973, 2868, 2983, 2886, 2997,
                     2905, 3016, 2916, 3016, 2920, 3005, 2920, 3005},
    std::vector<int>{3571, 2424, 3572, 2433, 3567, 2446, 3545, 2469, 3553, 2469, 3559, 2457, 3576, 2461, 3578, 2451,
                     3577, 2467, 3587, 2474, 3594, 2467, 3594, 2475, 3608, 2480, 3610, 2469, 3596, 2434, 3580, 2421,
                     3571, 2424, 3571, 2424},
    std::vector<int>{4095, 1229, 4093, 1228, 4081, 1217, 4073, 1234, 4071, 1253, 4064, 1278, 4076, 1293, 4087, 1283,
                     4097, 1285, 4110, 1286, 4101, 1291, 4121, 1285, 4119, 1276, 4104, 1258, 4096, 1258, 4093, 1268,
                     4094, 1258, 4096, 1245, 4095, 1229, 4095, 1229},
    std::vector<int>{4173, 1536, 4167, 1554, 4153, 1576, 4166, 1585, 4154, 1576, 4163, 1574, 4172, 1578, 4183, 1582,
                     4186, 1574, 4198, 1571, 4190, 1562, 4191, 1551, 4199, 1547, 4196, 1538, 4196, 1532, 4188, 1532,
                     4196, 1532, 4204, 1527, 4201, 1535, 4207, 1535, 4207, 1527, 4213, 1535, 4224, 1512, 4224, 1511,
                     4209, 1511, 4198, 1506, 4190, 1517, 4194, 1509, 4192, 1499, 4200, 1496, 4202, 1504, 4224, 1510,
                     4224, 1488, 4215, 1486, 4216, 1478, 4224, 1472, 4224, 1464, 4207, 1458, 4193, 1464, 4189, 1476,
                     4197, 1465, 4203, 1476, 4204, 1464, 4212, 1469, 4204, 1480, 4195, 1477, 4198, 1491, 4207, 1488,
                     4196, 1493, 4173, 1536, 4173, 1536},
    std::vector<int>{3934, 1537, 3932, 1553, 3936, 1580, 3944, 1579, 3950, 1595, 3960, 1604, 3968, 1630, 3964, 1639,
                     3963, 1650, 3960, 1666, 3968, 1673, 3968, 1664, 3983, 1662, 3975, 1640, 3981, 1627, 3980, 1618,
                     3970, 1606, 3959, 1589, 3973, 1578, 3975, 1562, 3971, 1570, 3972, 1556, 3964, 1540, 3959, 1537,
                     3943, 1537, 3934, 1537, 3934, 1537},
    std::vector<int>{4182, 1653, 4177, 1649, 4187, 1648, 4195, 1643, 4189, 1635, 4198, 1632, 4196, 1624, 4186, 1624,
                     4175, 1638, 4167, 1647, 4169, 1657, 4164, 1646, 4165, 1632, 4175, 1633, 4178, 1633, 4178, 1625,
                     4168, 1619, 4166, 1622, 4166, 1614, 4161, 1661, 4157, 1674, 4171, 1676, 4169, 1666, 4163, 1656,
                     4176, 1673, 4180, 1665, 4180, 1674, 4189, 1682, 4209, 1678, 4193, 1677, 4192, 1666, 4200, 1669,
                     4209, 1673, 4216, 1671, 4216, 1655, 4205, 1653, 4197, 1647, 4182, 1653, 4182, 1653},
    std::vector<int>{4200, 1619, 4196, 1620, 4200, 1632, 4195, 1642, 4207, 1648, 4211, 1636, 4205, 1627, 4203, 1636,
                     4200, 1619, 4200, 1619},
    std::vector<int>{4026, 1835, 4025, 1830, 4020, 1821, 4016, 1808, 4007, 1836, 4019, 1836, 4011, 1832, 4009, 1822,
                     4020, 1830, 4016, 1820, 4026, 1835, 4026, 1835},
    std::vector<int>{4199, 1384, 4192, 1379, 4182, 1389, 4190, 1393, 4192, 1402, 4206, 1412, 4216, 1401, 4208, 1401,
                     4209, 1393, 4199, 1384, 4199, 1384},
    std::vector<int>{3926, 1251, 3930, 1256, 3948, 1251, 3959, 1255, 3963, 1243, 3953, 1235, 3950, 1224, 3940, 1222,
                     3953, 1218, 3963, 1218, 3969, 1206, 3964, 1188, 3954, 1185, 3944, 1188, 3952, 1172, 3933, 1150,
                     3924, 1154, 3913, 1149, 3902, 1153, 3924, 1164, 3923, 1173, 3908, 1181, 3887, 1180, 3878, 1173,
                     3888, 1210, 3874, 1211, 3876, 1229, 3882, 1239, 3884, 1231, 3897, 1235, 3893, 1227, 3880, 1218,
                     3896, 1229, 3904, 1227, 3892, 1217, 3903, 1221, 3904, 1206, 3894, 1207, 3898, 1205, 3898, 1197,
                     3912, 1213, 3929, 1205, 3921, 1216, 3926, 1251, 3926, 1251},
    std::vector<int>{3926, 1354, 3922, 1360, 3958, 1389, 3953, 1374, 3962, 1375, 3972, 1373, 3984, 1390, 3992, 1388,
                     3989, 1384, 3997, 1384, 3991, 1352, 3982, 1338, 3968, 1332, 3960, 1322, 3955, 1299, 3954, 1307,
                     3943, 1311, 3946, 1321, 3935, 1329, 3946, 1335, 3956, 1338, 3959, 1348, 3956, 1361, 3964, 1362,
                     3955, 1370, 3952, 1360, 3951, 1368, 3940, 1363, 3926, 1354, 3926, 1354},
    std::vector<int>{3964, 1319, 3977, 1297, 3965, 1319, 3974, 1329, 3974, 1313, 3983, 1297, 3980, 1307, 3984, 1285,
                     3975, 1284, 3971, 1299, 3963, 1301, 3964, 1311, 3964, 1319, 3964, 1319},
    std::vector<int>{3687, 959, 3682, 948, 3672, 941, 3669, 928, 3681, 942, 3680, 927, 3678, 908, 3689, 908, 3698, 920,
                     3686, 901, 3696, 903, 3684, 896, 3678, 885, 3666, 890, 3664, 908, 3670, 921, 3665, 930, 3671, 947,
                     3678, 959, 3687, 959, 3687, 959},
    std::vector<int>{3452, 79, 3436, 104, 3437, 124, 3448, 146, 3456, 149, 3476, 141, 3460, 133, 3459, 125, 3452, 116,
                     3450, 107, 3467, 85, 3460, 75, 3452, 79, 3452, 79},
    std::vector<int>{3751, 927, 3754, 924, 3746, 910, 3738, 906, 3729, 914, 3737, 921, 3720, 923, 3719, 942, 3739, 929,
                     3751, 927, 3751, 927}
};

static const std::vector<std::vector<int>> water2Data = {
    std::vector<int>{-128, 4224, -128, 2734, -116, 2736, -109, 2749, -99, 2750, -101, 2734, -96, 2724, -90, 2708, -76,
                     2704, -61, 2690, -51, 2691, -40, 2674, -40, 2660, -29, 2647, -19, 2647, -11, 2643, -13, 2652, -15,
                     2671, -15, 2679, -23, 2679, -27, 2696, -37, 2706, -36, 2715, -45, 2708, -45, 2720, -43, 2732, -46,
                     2745, -34, 2757, -54, 2764, -62, 2769, -62, 2786, -69, 2800, -72, 2824, -77, 2838, -82, 2867, -86,
                     2884, -108, 2908, -101, 2919, -85, 2911, -72, 2897, -70, 2880, -60, 2880, -59, 2873, -48, 2873,
                     -46, 2859, -37, 2860, -28, 2850, -17, 2842, -17, 2834, -4, 2825, 8, 2825, 10, 2817, 12, 2799, 4,
                     2800, 8, 2797, 8, 2787, 22, 2796, 32, 2788, 52, 2801, 67, 2781, 78, 2747, 95, 2732, 97, 2720, 119,
                     2709, 109, 2695, 117, 2701, 114, 2689, 123, 2680, 128, 2670, 117, 2666, 120, 2654, 122, 2669, 131,
                     2668, 141, 2666, 143, 2676, 149, 2684, 148, 2692, 160, 2698, 152, 2698, 130, 2699, 133, 2717, 127,
                     2722, 118, 2722, 119, 2743, 102, 2760, 93, 2761, 83, 2772, 96, 2790, 116, 2800, 104, 2800, 85,
                     2802, 76, 2799, 80, 2809, 47, 2819, 31, 2818, 19, 2846, 21, 2851, 41, 2851, 61, 2850, 74, 2856, 77,
                     2865, 93, 2877, 100, 2895, 115, 2898, 138, 2890, 139, 2882, 139, 2890, 148, 2891, 170, 2891, 182,
                     2885, 197, 2894, 217, 2897, 193, 2896, 182, 2889, 152, 2899, 136, 2894, 113, 2905, 127, 2910, 137,
                     2919, 158, 2924, 167, 2932, 155, 2927, 143, 2927, 133, 2926, 123, 2914, 101, 2909, 94, 2896, 83,
                     2909, 91, 2914, 89, 2929, 81, 2939, 84, 2926, 89, 2915, 82, 2904, 92, 2893, 76, 2887, 74, 2877, 63,
                     2878, 54, 2880, 63, 2877, 49, 2869, 40, 2879, 40, 2887, 30, 2887, 22, 2892, 16, 2873, 1, 2873, -13,
                     2873, -27, 2891, -20, 2901, -1, 2907, -10, 2918, -19, 2910, -33, 2903, -43, 2895, -57, 2922, -60,
                     2940, -69, 2949, -85, 2954, -95, 2970, -99, 2987, -88, 2988, -75, 2988, -79, 2998, -93, 2998, -94,
                     2990, -101, 2998, -106, 2989, -128, 3002, -128, 4224, -128, 4224, 1249, 4224, 1247, 4199, 1231,
                     4132, 1221, 4130, 1230, 4148, 1214, 4165, 1198, 4171, 1162, 4169, 1134, 4155, 1091, 4128, 1068,
                     4096, 1025, 4052, 989, 4001, 924, 3927, 909, 3902, 904, 3882, 908, 3871, 909, 3858, 911, 3830, 905,
                     3799, 868, 3727, 827, 3685, 799, 3668, 787, 3655, 784, 3642, 782, 3582, 771, 3537, 765, 3481, 767,
                     3441, 786, 3409, 789, 3381, 785, 3371, 786, 3361, 776, 3339, 777, 3314, 770, 3305, 775, 3278, 734,
                     3220, 728, 3203, 729, 3178, 708, 3167, 695, 3147, 667, 3134, 666, 3126, 651, 3121, 645, 3113, 650,
                     3104, 630, 3089, 616, 3074, 615, 3053, 607, 3047, 607, 3035, 599, 3034, 603, 3026, 575, 2980, 532,
                     2939, 524, 2926, 509, 2903, 501, 2865, 509, 2844, 509, 2831, 526, 2809, 531, 2794, 540, 2718, 552,
                     2713, 543, 2711, 551, 2705, 537, 2701, 512, 2675, 503, 2708, 492, 2717, 502, 2705, 510, 2671, 493,
                     2656, 463, 2663, 485, 2654, 471, 2627, 474, 2614, 470, 2603, 475, 2588, 483, 2583, 486, 2573, 511,
                     2538, 550, 2523, 553, 2514, 561, 2507, 582, 2472, 595, 2460, 597, 2452, 605, 2447, 622, 2409, 638,
                     2357, 654, 2337, 663, 2311, 687, 2278, 718, 2256, 729, 2254, 739, 2249, 760, 2240, 776, 2227, 789,
                     2219, 786, 2213, 797, 2213, 819, 2191, 855, 2170, 865, 2163, 884, 2150, 897, 2147, 889, 2134, 898,
                     2146, 906, 2143, 907, 2126, 909, 2137, 917, 2138, 934, 2145, 958, 2142, 989, 2146, 996, 2166, 971,
                     2170, 967, 2181, 953, 2181, 933, 2170, 900, 2180, 888, 2187, 883, 2196, 868, 2204, 859, 2204, 872,
                     2219, 873, 2234, 884, 2226, 874, 2236, 876, 2244, 867, 2229, 870, 2221, 861, 2209, 842, 2213, 833,
                     2218, 812, 2228, 811, 2242, 796, 2258, 760, 2272, 740, 2289, 726, 2295, 704, 2319, 693, 2326, 689,
                     2349, 672, 2382, 671, 2415, 653, 2417, 643, 2443, 629, 2448, 623, 2457, 624, 2473, 613, 2512, 588,
                     2545, 576, 2549, 567, 2563, 534, 2585, 534, 2596, 547, 2625, 556, 2624, 571, 2640, 589, 2624, 573,
                     2642, 581, 2642, 584, 2651, 607, 2634, 615, 2638, 602, 2645, 596, 2658, 602, 2665, 610, 2665, 621,
                     2679, 620, 2695, 609, 2721, 589, 2747, 598, 2758, 594, 2808, 600, 2837, 583, 2842, 579, 2818, 575,
                     2830, 575, 2880, 584, 2898, 626, 2901, 630, 2912, 639, 2919, 653, 2920, 672, 2937, 683, 2934, 700,
                     2968, 706, 2979, 705, 2970, 711, 2986, 740, 3032, 748, 3038, 757, 3034, 769, 3035, 773, 3044, 788,
                     3053, 798, 3089, 824, 3100, 833, 3112, 844, 3105, 830, 3099, 837, 3087, 847, 3084, 845, 3072, 856,
                     3070, 858, 3062, 848, 3056, 851, 3048, 833, 3037, 852, 3047, 860, 3043, 877, 3052, 877, 3042, 881,
                     3028, 893, 3034, 893, 3046, 901, 3029, 914, 3030, 921, 3045, 938, 3041, 942, 3054, 948, 3043, 962,
                     3052, 962, 3043, 973, 3041, 974, 3050, 984, 3045, 988, 3056, 996, 3049, 1004, 3055, 1014, 3049,
                     1023, 3049, 1034, 3045, 1032, 3033, 1034, 3013, 1025, 3007, 1025, 2977, 1030, 2990, 1029, 3006,
                     1037, 3003, 1037, 3012, 1035, 3042, 1043, 3045, 1023, 3053, 1000, 3061, 997, 3053, 984, 3057, 982,
                     3047, 973, 3052, 967, 3040, 965, 3053, 950, 3048, 958, 3062, 947, 3057, 933, 3059, 929, 3047, 916,
                     3045, 915, 3034, 901, 3032, 902, 3040, 897, 3048, 881, 3038, 885, 3049, 880, 3055, 871, 3055, 860,
                     3046, 857, 3055, 857, 3074, 847, 3073, 850, 3086, 834, 3096, 846, 3101, 846, 3110, 858, 3106, 868,
                     3108, 890, 3123, 899, 3119, 910, 3120, 915, 3130, 901, 3128, 904, 3137, 917, 3140, 909, 3145, 901,
                     3139, 894, 3130, 892, 3139, 909, 3182, 946, 3217, 952, 3207, 947, 3195, 961, 3188, 954, 3175, 957,
                     3156, 949, 3157, 933, 3163, 923, 3153, 930, 3143, 934, 3156, 943, 3148, 943, 3140, 949, 3156, 957,
                     3155, 959, 3141, 968, 3139, 961, 3121, 973, 3118, 971, 3094, 973, 3104, 987, 3095, 974, 3106, 976,
                     3115, 988, 3104, 997, 3103, 989, 3107, 988, 3116, 976, 3116, 966, 3131, 987, 3135, 979, 3132, 984,
                     3124, 993, 3137, 1001, 3135, 971, 3133, 971, 3141, 961, 3146, 960, 3155, 961, 3169, 966, 3181, 953,
                     3195, 976, 3193, 1004, 3203, 1001, 3194, 1014, 3189, 1007, 3197, 997, 3208, 1012, 3227, 1020, 3227,
                     1023, 3218, 1032, 3203, 1026, 3219, 1027, 3228, 1024, 3218, 1023, 3227, 1011, 3241, 1014, 3249,
                     1025, 3254, 1057, 3270, 1068, 3271, 1077, 3284, 1088, 3304, 1100, 3300, 1098, 3292, 1100, 3302,
                     1125, 3305, 1133, 3310, 1122, 3306, 1107, 3308, 1116, 3320, 1122, 3353, 1129, 3361, 1137, 3357,
                     1153, 3350, 1144, 3353, 1139, 3362, 1122, 3377, 1132, 3387, 1146, 3408, 1161, 3413, 1166, 3423,
                     1170, 3412, 1179, 3406, 1177, 3395, 1166, 3396, 1155, 3397, 1166, 3394, 1157, 3387, 1170, 3377,
                     1169, 3391, 1177, 3391, 1193, 3374, 1188, 3366, 1196, 3367, 1210, 3360, 1203, 3350, 1195, 3347,
                     1196, 3338, 1205, 3338, 1198, 3329, 1207, 3336, 1207, 3353, 1221, 3357, 1219, 3348, 1220, 3362,
                     1233, 3367, 1243, 3364, 1257, 3363, 1260, 3360, 1276, 3360, 1268, 3344, 1270, 3327, 1282, 3329,
                     1270, 3327, 1269, 3339, 1281, 3339, 1269, 3339, 1274, 3354, 1282, 3349, 1280, 3360, 1290, 3360,
                     1287, 3348, 1287, 3356, 1296, 3343, 1291, 3359, 1304, 3348, 1320, 3351, 1311, 3339, 1321, 3322,
                     1331, 3318, 1343, 3325, 1330, 3300, 1338, 3305, 1336, 3287, 1344, 3285, 1342, 3294, 1350, 3273,
                     1355, 3276, 1355, 3288, 1359, 3280, 1358, 3270, 1345, 3270, 1360, 3269, 1352, 3255, 1365, 3245,
                     1373, 3248, 1376, 3238, 1380, 3221, 1386, 3209, 1372, 3201, 1375, 3196, 1367, 3196, 1376, 3196,
                     1367, 3191, 1377, 3193, 1380, 3188, 1365, 3188, 1361, 3177, 1368, 3167, 1357, 3164, 1353, 3155,
                     1361, 3152, 1346, 3149, 1341, 3141, 1342, 3133, 1334, 3128, 1335, 3119, 1322, 3112, 1330, 3109,
                     1320, 3099, 1319, 3091, 1310, 3073, 1321, 3073, 1312, 3075, 1321, 3074, 1317, 3082, 1326, 3081,
                     1330, 3094, 1334, 3102, 1341, 3110, 1345, 3121, 1337, 3128, 1345, 3130, 1347, 3122, 1357, 3117,
                     1359, 3111, 1359, 3103, 1363, 3093, 1363, 3102, 1360, 3113, 1350, 3129, 1364, 3150, 1358, 3160,
                     1368, 3164, 1373, 3176, 1381, 3183, 1389, 3176, 1381, 3184, 1381, 3200, 1391, 3198, 1398, 3206,
                     1413, 3186, 1391, 3215, 1379, 3228, 1382, 3238, 1384, 3230, 1397, 3226, 1395, 3228, 1407, 3228,
                     1394, 3229, 1397, 3248, 1391, 3258, 1380, 3260, 1377, 3283, 1361, 3291, 1359, 3303, 1343, 3303,
                     1352, 3317, 1350, 3326, 1341, 3328, 1330, 3322, 1320, 3331, 1332, 3325, 1354, 3334, 1357, 3343,
                     1347, 3347, 1335, 3349, 1346, 3351, 1337, 3357, 1345, 3360, 1337, 3361, 1338, 3369, 1328, 3363,
                     1334, 3382, 1325, 3398, 1345, 3401, 1346, 3388, 1347, 3397, 1358, 3402, 1361, 3393, 1370, 3383,
                     1371, 3394, 1362, 3399, 1387, 3402, 1374, 3401, 1388, 3398, 1376, 3392, 1388, 3396, 1375, 3389,
                     1387, 3391, 1375, 3383, 1388, 3391, 1404, 3390, 1387, 3377, 1396, 3379, 1413, 3374, 1411, 3386,
                     1407, 3400, 1435, 3408, 1436, 3399, 1419, 3387, 1427, 3376, 1420, 3366, 1429, 3370, 1427, 3378,
                     1422, 3389, 1430, 3387, 1430, 3395, 1435, 3409, 1453, 3416, 1445, 3406, 1443, 3399, 1443, 3386,
                     1454, 3397, 1462, 3391, 1465, 3382, 1473, 3390, 1474, 3382, 1458, 3364, 1477, 3383, 1473, 3394,
                     1482, 3395, 1478, 3410, 1494, 3408, 1494, 3416, 1493, 3426, 1502, 3427, 1510, 3436, 1514, 3428,
                     1505, 3420, 1514, 3428, 1513, 3419, 1522, 3417, 1507, 3411, 1520, 3412, 1518, 3401, 1526, 3394,
                     1522, 3403, 1523, 3411, 1532, 3426, 1543, 3438, 1548, 3429, 1554, 3443, 1568, 3435, 1570, 3456,
                     1579, 3457, 1588, 3465, 1580, 3459, 1579, 3469, 1580, 3459, 1569, 3457, 1563, 3441, 1555, 3444,
                     1546, 3438, 1537, 3442, 1528, 3440, 1526, 3453, 1537, 3458, 1542, 3450, 1537, 3460, 1526, 3461,
                     1532, 3486, 1528, 3502, 1527, 3523, 1536, 3528, 1522, 3525, 1522, 3557, 1513, 3583, 1511, 3591,
                     1509, 3602, 1509, 3593, 1473, 3664, 1450, 3709, 1429, 3764, 1417, 3824, 1458, 3825, 1491, 3840,
                     1504, 3850, 1522, 3849, 1526, 3834, 1518, 3833, 1530, 3834, 1532, 3826, 1527, 3823, 1535, 3823,
                     1535, 3820, 1544, 3820, 1560, 3816, 1571, 3811, 1563, 3799, 1554, 3800, 1543, 3811, 1552, 3804,
                     1551, 3796, 1559, 3802, 1556, 3787, 1547, 3790, 1556, 3786, 1564, 3784, 1560, 3776, 1552, 3778,
                     1564, 3775, 1570, 3788, 1586, 3800, 1574, 3783, 1588, 3799, 1582, 3787, 1597, 3787, 1595, 3778,
                     1580, 3769, 1579, 3780, 1579, 3769, 1581, 3747, 1589, 3731, 1604, 3729, 1603, 3720, 1605, 3730,
                     1596, 3733, 1608, 3738, 1609, 3747, 1617, 3731, 1633, 3721, 1631, 3710, 1615, 3710, 1614, 3723,
                     1610, 3715, 1616, 3708, 1632, 3708, 1642, 3702, 1651, 3702, 1635, 3681, 1625, 3681, 1616, 3693,
                     1621, 3685, 1615, 3662, 1625, 3660, 1635, 3637, 1644, 3637, 1655, 3630, 1648, 3615, 1680, 3638,
                     1678, 3599, 1664, 3598, 1661, 3590, 1672, 3572, 1687, 3560, 1701, 3556, 1711, 3562, 1716, 3571,
                     1724, 3570, 1735, 3561, 1753, 3559, 1762, 3547, 1740, 3551, 1727, 3545, 1716, 3531, 1714, 3517,
                     1723, 3512, 1734, 3526, 1744, 3530, 1752, 3525, 1780, 3522, 1774, 3507, 1749, 3508, 1742, 3494,
                     1729, 3488, 1751, 3468, 1764, 3474, 1777, 3478, 1798, 3472, 1807, 3473, 1796, 3475, 1794, 3495,
                     1782, 3507, 1779, 3540, 1792, 3530, 1810, 3485, 1843, 3426, 1872, 3393, 1873, 3383, 1860, 3397,
                     1841, 3405, 1845, 3413, 1835, 3420, 1835, 3429, 1824, 3449, 1803, 3448, 1807, 3459, 1809, 3470,
                     1798, 3472, 1803, 3453, 1794, 3449, 1796, 3439, 1788, 3432, 1787, 3418, 1802, 3409, 1815, 3391,
                     1844, 3380, 1847, 3372, 1844, 3359, 1854, 3349, 1853, 3337, 1876, 3335, 1880, 3313, 1901, 3306,
                     1908, 3298, 1880, 3315, 1882, 3333, 1868, 3337, 1884, 3336, 1872, 3344, 1882, 3351, 1870, 3345,
                     1870, 3355, 1881, 3360, 1874, 3370, 1949, 3282, 1971, 3261, 2006, 3241, 2018, 3223, 2016, 3204,
                     2004, 3208, 2001, 3216, 1979, 3235, 1962, 3244, 1960, 3252, 1951, 3245, 1956, 3256, 1947, 3245,
                     1944, 3253, 1953, 3258, 1943, 3254, 1933, 3264, 1925, 3279, 1912, 3281, 1908, 3291, 1904, 3281,
                     1909, 3250, 1915, 3238, 1924, 3238, 1917, 3224, 1904, 3222, 1899, 3187, 1905, 3178, 1902, 3165,
                     1912, 3166, 1913, 3150, 1911, 3160, 1907, 3170, 1918, 3194, 1927, 3194, 1936, 3184, 1951, 3187,
                     1966, 3178, 1964, 3169, 1973, 3167, 1982, 3159, 1995, 3160, 1984, 3168, 1970, 3169, 1975, 3181,
                     1992, 3194, 2006, 3176, 1992, 3168, 1995, 3160, 1995, 3151, 1992, 3143, 2004, 3136, 2005, 3122,
                     2015, 3113, 2029, 3111, 2027, 3099, 2030, 3111, 2032, 3122, 2033, 3131, 2040, 3117, 2034, 3104,
                     2028, 3084, 2038, 3099, 2049, 3097, 2049, 3111, 2050, 3091, 2063, 3095, 2055, 3091, 2067, 3083,
                     2063, 3072, 2056, 3062, 2061, 3048, 2070, 3041, 2089, 3046, 2100, 3055, 2102, 3063, 2112, 3053,
                     2117, 3067, 2135, 3066, 2157, 3075, 2168, 3085, 2170, 3073, 2159, 3071, 2151, 3057, 2162, 3052,
                     2161, 3042, 2167, 3033, 2160, 3042, 2166, 3033, 2153, 3047, 2145, 3049, 2139, 3058, 2149, 3057,
                     2145, 3066, 2146, 3058, 2135, 3053, 2141, 3044, 2133, 3044, 2120, 3039, 2130, 3043, 2143, 3039,
                     2130, 3031, 2120, 3031, 2128, 3029, 2139, 3034, 2131, 3029, 2144, 3026, 2149, 3016, 2139, 3014,
                     2136, 3023, 2128, 3024, 2111, 3022, 2105, 3013, 2112, 3005, 2112, 2997, 2101, 2994, 2113, 2997,
                     2110, 2989, 2117, 2980, 2121, 2969, 2123, 2959, 2122, 2972, 2143, 2972, 2146, 2953, 2134, 2950,
                     2146, 2952, 2128, 2948, 2148, 2944, 2138, 2937, 2151, 2942, 2151, 2925, 2169, 2922, 2169, 2913,
                     2164, 2901, 2172, 2905, 2164, 2899, 2172, 2904, 2173, 2896, 2182, 2898, 2171, 2891, 2197, 2906,
                     2222, 2930, 2233, 2910, 2223, 2900, 2214, 2891, 2224, 2898, 2222, 2890, 2238, 2893, 2247, 2903,
                     2243, 2890, 2234, 2890, 2243, 2890, 2240, 2879, 2231, 2875, 2222, 2879, 2230, 2874, 2218, 2869,
                     2204, 2876, 2212, 2882, 2189, 2864, 2202, 2860, 2215, 2861, 2225, 2864, 2223, 2850, 2235, 2849,
                     2247, 2857, 2249, 2849, 2247, 2858, 2254, 2857, 2254, 2869, 2265, 2863, 2266, 2852, 2258, 2849,
                     2247, 2840, 2239, 2847, 2245, 2836, 2227, 2821, 2224, 2811, 2224, 2798, 2213, 2786, 2201, 2782,
                     2183, 2795, 2185, 2785, 2169, 2795, 2182, 2791, 2189, 2777, 2187, 2789, 2194, 2781, 2202, 2779,
                     2201, 2767, 2206, 2783, 2221, 2785, 2219, 2769, 2225, 2753, 2215, 2742, 2205, 2729, 2197, 2729,
                     2194, 2738, 2194, 2739, 2194, 2755, 2182, 2752, 2174, 2747, 2173, 2755, 2160, 2752, 2156, 2760,
                     2143, 2768, 2147, 2758, 2156, 2753, 2171, 2755, 2173, 2743, 2169, 2731, 2174, 2719, 2166, 2716,
                     2166, 2734, 2153, 2737, 2147, 2719, 2131, 2733, 2122, 2729, 2120, 2717, 2111, 2721, 2109, 2729,
                     2101, 2738, 2102, 2728, 2096, 2720, 2089, 2733, 2089, 2725, 2095, 2716, 2094, 2708, 2085, 2712,
                     2085, 2696, 2076, 2696, 2072, 2685, 2059, 2697, 2049, 2692, 2032, 2681, 2025, 2666, 2003, 2662,
                     2024, 2665, 2013, 2642, 1998, 2644, 1987, 2638, 1978, 2642, 1967, 2625, 1964, 2614, 1951, 2608,
                     1930, 2593, 1918, 2595, 1926, 2593, 1915, 2589, 1904, 2598, 1900, 2594, 1900, 2584, 1890, 2593,
                     1895, 2584, 1905, 2596, 1911, 2585, 1956, 2606, 1967, 2613, 1969, 2624, 1978, 2628, 2004, 2639,
                     2012, 2632, 2026, 2655, 2049, 2671, 2059, 2679, 2058, 2691, 2072, 2682, 2078, 2690, 2094, 2662,
                     2087, 2688, 2094, 2698, 2110, 2698, 2114, 2706, 2106, 2713, 2119, 2709, 2130, 2706, 2123, 2698,
                     2117, 2680, 2108, 2678, 2116, 2679, 2113, 2655, 2117, 2647, 2105, 2636, 2099, 2604, 2094, 2591,
                     2088, 2575, 2088, 2564, 2098, 2578, 2089, 2586, 2096, 2588, 2096, 2598, 2105, 2606, 2103, 2616,
                     2107, 2625, 2110, 2637, 2118, 2641, 2131, 2626, 2121, 2635, 2125, 2648, 2116, 2655, 2115, 2668,
                     2123, 2673, 2123, 2681, 2131, 2676, 2123, 2681, 2122, 2673, 2122, 2689, 2131, 2689, 2124, 2697,
                     2131, 2705, 2125, 2716, 2140, 2715, 2141, 2707, 2145, 2698, 2140, 2690, 2130, 2684, 2140, 2689,
                     2141, 2697, 2152, 2697, 2145, 2714, 2158, 2732, 2160, 2716, 2166, 2704, 2175, 2712, 2189, 2715,
                     2198, 2718, 2218, 2708, 2211, 2697, 2214, 2686, 2206, 2689, 2196, 2694, 2199, 2685, 2209, 2684,
                     2219, 2687, 2232, 2692, 2234, 2683, 2231, 2693, 2219, 2691, 2219, 2705, 2222, 2713, 2229, 2703,
                     2223, 2714, 2219, 2728, 2228, 2711, 2236, 2709, 2230, 2717, 2239, 2719, 2239, 2727, 2230, 2728,
                     2243, 2727, 2243, 2739, 2249, 2751, 2259, 2749, 2267, 2747, 2258, 2739, 2268, 2742, 2263, 2733,
                     2268, 2745, 2281, 2736, 2290, 2737, 2289, 2729, 2280, 2735, 2272, 2737, 2277, 2727, 2285, 2730,
                     2269, 2715, 2268, 2724, 2262, 2715, 2264, 2707, 2276, 2711, 2276, 2719, 2284, 2718, 2291, 2709,
                     2299, 2706, 2308, 2710, 2316, 2713, 2319, 2705, 2330, 2694, 2326, 2667, 2325, 2656, 2326, 2666,
                     2328, 2676, 2339, 2679, 2347, 2680, 2348, 2668, 2340, 2674, 2350, 2664, 2335, 2670, 2347, 2664,
                     2334, 2668, 2350, 2663, 2361, 2659, 2363, 2647, 2352, 2640, 2360, 2639, 2369, 2642, 2363, 2632,
                     2376, 2630, 2385, 2623, 2398, 2630, 2394, 2617, 2378, 2613, 2368, 2596, 2379, 2613, 2390, 2618,
                     2407, 2612, 2418, 2613, 2433, 2625, 2441, 2618, 2439, 2607, 2429, 2605, 2426, 2597, 2418, 2593,
                     2405, 2582, 2392, 2577, 2405, 2581, 2414, 2590, 2427, 2595, 2437, 2600, 2438, 2584, 2439, 2570,
                     2436, 2559, 2441, 2569, 2436, 2581, 2445, 2591, 2453, 2584, 2452, 2569, 2456, 2573, 2456, 2561,
                     2450, 2541, 2438, 2517, 2453, 2536, 2453, 2547, 2464, 2553, 2473, 2550, 2479, 2542, 2493, 2550,
                     2489, 2535, 2493, 2547, 2503, 2550, 2499, 2534, 2487, 2519, 2494, 2527, 2500, 2519, 2494, 2508,
                     2502, 2516, 2492, 2498, 2508, 2510, 2503, 2491, 2493, 2482, 2505, 2492, 2507, 2501, 2521, 2474,
                     2519, 2466, 2533, 2460, 2551, 2454, 2550, 2439, 2538, 2436, 2534, 2424, 2550, 2433, 2561, 2435,
                     2577, 2440, 2569, 2426, 2560, 2429, 2548, 2429, 2558, 2427, 2575, 2420, 2567, 2416, 2550, 2402,
                     2540, 2404, 2532, 2403, 2541, 2397, 2551, 2401, 2559, 2401, 2569, 2400, 2580, 2407, 2573, 2392,
                     2576, 2381, 2567, 2381, 2579, 2375, 2561, 2368, 2552, 2365, 2547, 2357, 2554, 2368, 2550, 2377,
                     2548, 2377, 2548, 2368, 2539, 2363, 2545, 2375, 2547, 2385, 2541, 2390, 2533, 2390, 2546, 2385,
                     2543, 2374, 2532, 2359, 2528, 2350, 2528, 2340, 2533, 2327, 2535, 2337, 2535, 2328, 2536, 2337,
                     2537, 2329, 2529, 2341, 2529, 2349, 2529, 2358, 2537, 2358, 2546, 2349, 2541, 2324, 2533, 2326,
                     2529, 2317, 2537, 2316, 2541, 2324, 2546, 2313, 2551, 2305, 2542, 2300, 2551, 2305, 2549, 2297,
                     2553, 2286, 2545, 2278, 2555, 2280, 2557, 2268, 2543, 2268, 2553, 2267, 2553, 2257, 2561, 2256,
                     2574, 2239, 2565, 2238, 2556, 2242, 2538, 2236, 2546, 2233, 2560, 2237, 2573, 2235, 2583, 2225,
                     2565, 2226, 2573, 2223, 2578, 2212, 2567, 2215, 2578, 2212, 2580, 2224, 2588, 2213, 2576, 2211,
                     2568, 2210, 2560, 2215, 2524, 2219, 2518, 2229, 2522, 2219, 2561, 2205, 2585, 2205, 2613, 2180,
                     2602, 2186, 2609, 2177, 2600, 2185, 2607, 2177, 2599, 2184, 2590, 2182, 2608, 2176, 2587, 2173,
                     2568, 2165, 2588, 2171, 2604, 2169, 2614, 2167, 2624, 2153, 2621, 2142, 2629, 2151, 2634, 2142,
                     2592, 2140, 2617, 2140, 2602, 2139, 2613, 2137, 2626, 2141, 2625, 2126, 2621, 2134, 2609, 2133,
                     2583, 2127, 2578, 2122, 2586, 2122, 2610, 2122, 2631, 2118, 2623, 2116, 2622, 2106, 2614, 2104,
                     2621, 2100, 2611, 2100, 2619, 2100, 2611, 2098, 2619, 2096, 2617, 2088, 2618, 2081, 2626, 2081,
                     2625, 2071, 2623, 2060, 2623, 2052, 2628, 2063, 2637, 2052, 2627, 2048, 2614, 2046, 2616, 2038,
                     2615, 2046, 2623, 2039, 2630, 2047, 2642, 2037, 2654, 2038, 2665, 2027, 2660, 2016, 2668, 2008,
                     2651, 2007, 2650, 2015, 2642, 2014, 2630, 2013, 2615, 2010, 2609, 2001, 2594, 2006, 2600, 1998,
                     2569, 1988, 2560, 1993, 2544, 1979, 2534, 1973, 2546, 1971, 2553, 1979, 2561, 1979, 2574, 1977,
                     2589, 1980, 2600, 1989, 2612, 1993, 2621, 1996, 2627, 1986, 2619, 1979, 2628, 1985, 2644, 1982,
                     2645, 1973, 2645, 1982, 2654, 1976, 2660, 1967, 2661, 1950, 2636, 1947, 2645, 1951, 2656, 1944,
                     2659, 1932, 2647, 1932, 2653, 1923, 2642, 1916, 2634, 1916, 2628, 1904, 2611, 1886, 2602, 1885,
                     2602, 1877, 2623, 1880, 2620, 1872, 2610, 1871, 2625, 1870, 2635, 1876, 2651, 1875, 2654, 1865,
                     2643, 1861, 2658, 1859, 2659, 1873, 2666, 1852, 2656, 1852, 2651, 1844, 2616, 1843, 2638, 1839,
                     2621, 1832, 2635, 1832, 2620, 1816, 2630, 1820, 2624, 1809, 2629, 1818, 2645, 1832, 2654, 1830,
                     2649, 1822, 2649, 1813, 2654, 1823, 2666, 1830, 2670, 1846, 2682, 1844, 2696, 1852, 2709, 1834,
                     2700, 1832, 2707, 1822, 2699, 1821, 2709, 1819, 2711, 1809, 2728, 1808, 2739, 1799, 2730, 1788,
                     2714, 1780, 2695, 1788, 2680, 1779, 2673, 1787, 2663, 1781, 2650, 1776, 2639, 1775, 2647, 1769,
                     2638, 1763, 2629, 1758, 2614, 1740, 2622, 1746, 2630, 1753, 2638, 1754, 2666, 1774, 2702, 1771,
                     2716, 1767, 2728, 1770, 2723, 1762, 2708, 1766, 2676, 1764, 2712, 1761, 2691, 1750, 2689, 1728,
                     2696, 1744, 2700, 1752, 2716, 1762, 2724, 1758, 2747, 1755, 2745, 1745, 2753, 1751, 2751, 1769,
                     2742, 1821, 2729, 1831, 2739, 1825, 2735, 1831, 2727, 1831, 2737, 1832, 2729, 1836, 2739, 1840,
                     2730, 1844, 2725, 1852, 2736, 1847, 2735, 1858, 2731, 1871, 2732, 1861, 2722, 1868, 2730, 1875,
                     2725, 1889, 2723, 1899, 2714, 1903, 2722, 1907, 2714, 1907, 2715, 1915, 2717, 1924, 2712, 1938,
                     2697, 1944, 2707, 1951, 2708, 1960, 2700, 1956, 2703, 1972, 2705, 1983, 2706, 1998, 2699, 2008,
                     2708, 2008, 2704, 2009, 2704, 2029, 2694, 2049, 2681, 2049, 2697, 2049, 2694, 2057, 2691, 2073,
                     2699, 2089, 2694, 2109, 2690, 2171, 2687, 2180, 2688, 2197, 2682, 2243, 2675, 2252, 2674, 2265,
                     2682, 2290, 2674, 2287, 2679, 2300, 2671, 2305, 2662, 2299, 2651, 2289, 2654, 2300, 2667, 2308,
                     2681, 2323, 2710, 2049, 2733, 1891, 2764, 1727, 2776, 1685, 2767, 1679, 2765, 1683, 2754, 1683,
                     2743, 1689, 2734, 1703, 2720, 1709, 2711, 1708, 2699, 1700, 2690, 1686, 2673, 1680, 2681, 1678,
                     2681, 1665, 2678, 1656, 2675, 1639, 2680, 1631, 2681, 1644, 2688, 1654, 2691, 1667, 2694, 1673,
                     2694, 1683, 2699, 1691, 2710, 1697, 2719, 1697, 2734, 1688, 2756, 1669, 2746, 1666, 2748, 1657,
                     2757, 1661, 2765, 1660, 2762, 1670, 2754, 1671, 2767, 1674, 2781, 1626, 2810, 1522, 2794, 1521,
                     2783, 1526, 2776, 1535, 2765, 1535, 2744, 1531, 2734, 1510, 2745, 1515, 2762, 1525, 2766, 1513,
                     2764, 1505, 2781, 1510, 2786, 1520, 2809, 1520, 2812, 1494, 2828, 1438, 2850, 1332, 2862, 1242,
                     2863, 1186, 2858, 1103, 2849, 1075, 2847, 1025, 2832, 985, 2814, 958, 2810, 966, 2796, 966, 2794,
                     977, 2811, 986, 2817, 1021, 2830, 1025, 2739, 1025, 2831, 1026, 2830, 1057, 2842, 1063, 2845, 1081,
                     2836, 1076, 2850, 1090, 2848, 1101, 2855, 1117, 2859, 1174, 2853, 1235, 2844, 1227, 2836, 1240,
                     2835, 1232, 2827, 1235, 2835, 1242, 2838, 1253, 2846, 1252, 2844, 1263, 2842, 1254, 2828, 1252,
                     2831, 1261, 2839, 1279, 2828, 1273, 2811, 1286, 2820, 1277, 2827, 1261, 2824, 1246, 2808, 1252,
                     2806, 1262, 2807, 1250, 2794, 1258, 2791, 1266, 2785, 1277, 2776, 1277, 2788, 1262, 2768, 1263,
                     2759, 1272, 2751, 1272, 2775, 1260, 2790, 1259, 2797, 1240, 2784, 1243, 2802, 1233, 2777, 1234,
                     2792, 1228, 2798, 1220, 2800, 1225, 2809, 1225, 2811, 1217, 2804, 1215, 2812, 1215, 2820, 1205,
                     2829, 1202, 2842, 1199, 2854, 1187, 2851, 1160, 2827, 1161, 2806, 1154, 2797, 1161, 2788, 1159,
                     2776, 1176, 2754, 1175, 2744, 1183, 2740, 1195, 2724, 1204, 2713, 1198, 2708, 1213, 2699, 1221,
                     2703, 1229, 2705, 1209, 2710, 1195, 2723, 1193, 2724, 1179, 2739, 1170, 2755, 1166, 2784, 1148,
                     2797, 1145, 2797, 1134, 2785, 1123, 2794, 1125, 2799, 1134, 2811, 1136, 2819, 1131, 2829, 1145,
                     2848, 1143, 2850, 1123, 2846, 1108, 2821, 1092, 2811, 1094, 2788, 1088, 2770, 1081, 2762, 1081,
                     2734, 1068, 2712, 1051, 2704, 1048, 2653, 1025, 2626, 1005, 2606, 1020, 2598, 1022, 2579, 1020,
                     2565, 1004, 2548, 1023, 2540, 1034, 2511, 1046, 2520, 1038, 2516, 1024, 2494, 1012, 2478, 1004,
                     2465, 1002, 2447, 992, 2429, 1008, 2429, 1016, 2444, 991, 2428, 951, 2424, 940, 2402, 935, 2393,
                     923, 2397, 914, 2372, 915, 2356, 945, 2341, 955, 2319, 960, 2308, 959, 2304, 970, 2295, 978, 2284,
                     980, 2288, 963, 2275, 966, 2264, 962, 2261, 948, 2247, 958, 2242, 944, 2231, 944, 2223, 938, 2208,
                     948, 2194, 947, 2180, 922, 2166, 911, 2120, 900, 2099, 866, 2072, 842, 2062, 814, 2047, 809, 2057,
                     808, 2066, 816, 2073, 841, 2100, 866, 2122, 900, 2169, 909, 2181, 920, 2189, 940, 2197, 945, 2207,
                     945, 2221, 935, 2241, 938, 2250, 948, 2258, 945, 2254, 944, 2264, 944, 2265, 958, 2283, 955, 2283,
                     943, 2283, 955, 2291, 962, 2288, 976, 2301, 969, 2302, 954, 2312, 951, 2302, 939, 2312, 951, 2331,
                     947, 2341, 939, 2353, 918, 2376, 901, 2392, 899, 2403, 905, 2410, 915, 2434, 923, 2443, 897, 2449,
                     886, 2458, 880, 2452, 849, 2450, 817, 2451, 828, 2455, 820, 2484, 802, 2500, 809, 2509, 786, 2517,
                     740, 2528, 737, 2529, 728, 2521, 724, 2523, 692, 2527, 667, 2544, 646, 2561, 636, 2576, 628, 2592,
                     611, 2605, 617, 2619, 589, 2588, 563, 2612, 577, 2624, 560, 2617, 551, 2597, 542, 2619, 548, 2629,
                     561, 2641, 544, 2646, 530, 2641, 506, 2649, 467, 2641, 460, 2652, 461, 2647, 496, 2652, 506, 2672,
                     497, 2674, 489, 2683, 466, 2710, 452, 2710, 447, 2687, 447, 2681, 435, 2691, 414, 2689, 388, 2698,
                     373, 2688, 370, 2690, 362, 2698, 371, 2701, 360, 2712, 349, 2693, 330, 2715, 349, 2732, 333, 2772,
                     327, 2776, 313, 2766, 291, 2774, 286, 2775, 269, 2779, 245, 2769, 219, 2770, 200, 2771, 198, 2771,
                     217, 2781, 242, 2778, 255, 2789, 269, 2802, 270, 2816, 219, 2809, 246, 2804, 273, 2791, 273, 2781,
                     259, 2778, 273, 2781, 283, 2772, 293, 2780, 320, 2773, 332, 2765, 334, 2773, 340, 2781, 342, 2771,
                     351, 2773, 359, 2765, 363, 2763, 353, 2770, 343, 2762, 350, 2754, 351, 2761, 342, 2758, 334, 2738,
                     337, 2724, 352, 2714, 355, 2692, 390, 2696, 410, 2688, 426, 2686, 440, 2710, 438, 2714, 453, 2705,
                     463, 2692, 467, 2678, 503, 2667, 511, 2667, 531, 2660, 549, 2657, 558, 2648, 577, 2639, 593, 2636,
                     605, 2628, 617, 2618, 623, 2611, 637, 2612, 647, 2648, 642, 2652, 631, 2680, 636, 2695, 628, 2689,
                     611, 2691, 606, 2680, 606, 2665, 598, 2693, 601, 2719, 614, 2682, 587, 2693, 585, 2725, 604, 2703,
                     584, 2717, 587, 2719, 579, 2709, 572, 2718, 574, 2705, 560, 2717, 560, 2726, 549, 2742, 557, 2740,
                     548, 2762, 530, 2771, 528, 2744, 515, 2760, 517, 2775, 513, 2774, 505, 2772, 493, 2783, 484, 2777,
                     475, 2768, 473, 2783, 474, 2790, 452, 2790, 442, 2782, 432, 2794, 428, 2792, 420, 2801, 402, 2807,
                     398, 2807, 390, 2822, 377, 2834, 342, 2845, 336, 2845, 328, 2867, 287, 2866, 272, 2881, 247, 2883,
                     232, 2903, 188, 2934, 195, 2949, 205, 2940, 206, 2931, 197, 2913, 231, 2899, 250, 2900, 262, 2889,
                     292, 2883, 304, 2840, 375, 2838, 385, 2831, 398, 2826, 407, 2818, 413, 2818, 421, 2806, 440, 2808,
                     449, 2804, 459, 2806, 475, 2800, 484, 2803, 498, 2794, 527, 2803, 539, 2814, 534, 2824, 522, 2849,
                     520, 2863, 487, 2859, 470, 2863, 455, 2905, 395, 2904, 379, 2925, 355, 2925, 344, 2917, 328, 2916,
                     279, 2937, 235, 2951, 215, 2950, 206, 2919, 278, 2921, 332, 2927, 342, 2950, 353, 2964, 337, 2974,
                     333, 2989, 342, 2999, 341, 3014, 334, 3014, 326, 3026, 331, 3043, 337, 3042, 324, 3051, 313, 3059,
                     335, 3067, 337, 3067, 329, 3089, 320, 3123, 339, 3106, 323, 3103, 315, 3108, 323, 3116, 316, 3106,
                     310, 3102, 298, 3092, 300, 3094, 292, 3090, 284, 3089, 263, 3088, 247, 3094, 233, 3083, 233, 3079,
                     212, 3083, 183, 3073, 175, 3082, 160, 3078, 176, 3081, 211, 3091, 211, 3091, 225, 3101, 231, 3107,
                     243, 3112, 254, 3115, 241, 3125, 229, 3125, 216, 3134, 215, 3135, 205, 3136, 195, 3128, 190, 3121,
                     205, 3110, 220, 3099, 209, 3109, 214, 3124, 185, 3134, 177, 3138, 168, 3148, 152, 3142, 174, 3152,
                     166, 3162, 160, 3165, 149, 3160, 137, 3152, 130, 3161, 129, 3169, 133, 3173, 123, 3189, 124, 3195,
                     120, 3195, 105, 3196, 91, 3198, 101, 3204, 92, 3203, 101, 3213, 94, 3208, 112, 3213, 100, 3221,
                     100, 3227, 80, 3204, 71, 3215, 71, 3211, 60, 3221, 59, 3218, 68, 3229, 73, 3237, 59, 3235, 67,
                     3247, 68, 3255, 59, 3263, 51, 3271, 41, 3261, 78, 3267, 69, 3281, 69, 3276, 61, 3284, 59, 3281, 47,
                     3292, 31, 3300, 26, 3314, 25, 3322, 0, 3313, -4, 3317, 8, 3309, 2, 3313, -15, 3321, -13, 3337, -42,
                     3345, -62, 3345, -47, 3353, -42, 3365, -42, 3369, -57, 3360, -67, 3368, -65, 3363, -75, 3372, -60,
                     3374, -71, 3377, -58, 3384, -79, 3386, -71, 3385, -62, 3398, -74, 3402, -93, 3412, -103, 3414, -81,
                     3418, -73, 3409, -72, 3414, -60, 3423, -60, 3424, -69, 3433, -70, 3437, -80, 3440, -92, 3443, -83,
                     3448, -75, 3445, -66, 3447, -57, 3439, -47, 3430, -54, 3427, -41, 3446, -42, 3451, -63, 3459, -72,
                     3471, -83, 3478, -99, 3476, -88, 3480, -83, 3480, -91, 3488, -96, 3483, -121, 3490, -102, 3490,
                     -110, 3495, -100, 3496, -108, 3505, -120, 3502, -128, 3508, -119, 3497, -103, 3507, -71, 3517, -77,
                     3526, -97, 3517, -103, 3517, -121, 3520, -113, 3539, -113, 3543, -126, 3550, -128, 3562, -128,
                     3568, -118, 3571, -128, 3582, -108, 3585, -123, 3584, -128, 4224, -128, 4224, 28, 4216, 28, 4216,
                     32, 4224, 32, 4220, 45, 4212, 31, 4166, 14, 4145, 14, 4156, 19, 4169, 17, 4164, 25, 4180, 56, 4172,
                     65, 4165, 55, 4139, 42, 4141, 56, 4130, 60, 4130, 70, 4123, 59, 4113, 56, 4113, 48, 4121, 58, 4132,
                     50, 4132, 37, 4124, 35, 4120, 23, 4105, 32, 4110, 43, 4106, 53, 4109, 63, 4104, 51, 4095, 52, 4091,
                     40, 4107, 26, 4111, 17, 4124, 22, 4147, 26, 4142, 20, 4125, 20, 4106, 5, 4095, 15, 4079, 25, 4077,
                     35, 4068, 35, 4059, 28, 4073, 29, 4047, 24, 4068, 47, 4063, 104, 4068, 100, 4068, 85, 4070, 70,
                     4074, 81, 4074, 89, 4069, 100, 4059, 114, 4063, 125, 4041, 131, 4029, 146, 4032, 167, 4021, 160,
                     4011, 142, 4012, 127, 4027, 115, 4026, 124, 4033, 112, 4045, 113, 4058, 104, 3959, 139, 3939, 136,
                     3944, 144, 3934, 136, 3891, 126, 3850, 107, 3815, 101, 3776, 100, 3776, 114, 3774, 104, 3743, 92,
                     3709, 50, 3696, 47, 3690, 104, 3686, 124, 3688, 114, 3693, 97, 3714, 110, 3721, 100, 3716, 84,
                     3729, 90, 3722, 72, 3740, 94, 3732, 90, 3724, 99, 3739, 96, 3766, 111, 3762, 128, 3764, 154, 3764,
                     163, 3762, 172, 3750, 176, 3748, 174, 3748, 163, 3753, 155, 3732, 127, 3723, 149, 3731, 152, 3736,
                     163, 3725, 155, 3717, 146, 3701, 137, 3680, 146, 3646, 143, 3649, 154, 3667, 162, 3671, 171, 3668,
                     182, 3665, 174, 3659, 163, 3651, 161, 3631, 155, 3641, 152, 3647, 137, 3636, 139, 3625, 129, 3579,
                     133, 3574, 138, 3574, 130, 3620, 127, 3634, 114, 3648, 111, 3644, 128, 3654, 114, 3652, 98, 3642,
                     88, 3603, 83, 3581, 72, 3572, 63, 3560, 74, 3562, 83, 3567, 71, 3568, 79, 3560, 90, 3560, 81, 3554,
                     109, 3563, 117, 3579, 154, 3591, 202, 3606, 211, 3604, 232, 3594, 220, 3602, 221, 3603, 216, 3590,
                     216, 3584, 208, 3567, 199, 3563, 188, 3557, 163, 3536, 167, 3534, 178, 3544, 204, 3534, 201, 3517,
                     204, 3506, 197, 3489, 199, 3480, 182, 3480, 152, 3452, 160, 3457, 178, 3443, 162, 3445, 151, 3456,
                     154, 3468, 142, 3479, 147, 3492, 146, 3501, 139, 3510, 126, 3517, 137, 3516, 157, 3508, 169, 3501,
                     173, 3501, 181, 3520, 180, 3521, 162, 3526, 152, 3539, 151, 3536, 139, 3519, 125, 3503, 129, 3481,
                     137, 3454, 124, 3433, 135, 3411, 138, 3408, 147, 3385, 150, 3378, 158, 3356, 148, 3354, 158, 3352,
                     166, 3340, 177, 3325, 195, 3322, 224, 3329, 238, 3352, 228, 3343, 234, 3336, 243, 3327, 254, 3328,
                     279, 3335, 304, 3332, 345, 3327, 334, 3326, 303, 3331, 293, 3323, 290, 3318, 279, 3294, 237, 3237,
                     212, 3230, 221, 3215, 219, 3219, 238, 3204, 255, 3216, 266, 3218, 284, 3218, 273, 3232, 275, 3245,
                     267, 3246, 283, 3252, 272, 3260, 282, 3251, 296, 3253, 319, 3243, 334, 3245, 359, 3235, 335, 3234,
                     317, 3229, 307, 3215, 301, 3212, 293, 3201, 292, 3197, 284, 3186, 281, 3181, 273, 3176, 283, 3181,
                     305, 3164, 321, 3166, 333, 3183, 349, 3182, 371, 3191, 379, 3179, 390, 3181, 415, 3163, 396, 3151,
                     374, 3146, 353, 3137, 356, 3124, 368, 3121, 356, 3095, 352, 3084, 345, 3073, 352, 3073, 360, 3067,
                     369, 3059, 367, 3054, 351, 3046, 354, 3035, 358, 3033, 368, 3032, 381, 3041, 381, 3040, 403, 3048,
                     413, 3056, 410, 3060, 419, 3057, 429, 3055, 413, 3039, 425, 3026, 419, 3022, 410, 3031, 406, 3008,
                     384, 3009, 373, 3003, 382, 2988, 386, 2991, 396, 2982, 397, 2980, 381, 2964, 385, 2973, 372, 2953,
                     364, 2926, 392, 2916, 389, 2917, 404, 2905, 414, 2885, 444, 2876, 464, 2889, 462, 2899, 466, 2911,
                     456, 2900, 467, 2912, 480, 2938, 493, 2937, 509, 2926, 506, 2921, 515, 2932, 501, 2926, 487, 2912,
                     482, 2903, 469, 2894, 465, 2884, 464, 2876, 474, 2878, 489, 2869, 506, 2865, 521, 2869, 532, 2862,
                     521, 2864, 539, 2857, 540, 2857, 530, 2830, 530, 2825, 540, 2821, 548, 2820, 558, 2812, 559, 2804,
                     569, 2794, 578, 2794, 592, 2803, 590, 2807, 598, 2799, 606, 2807, 599, 2820, 600, 2820, 610, 2807,
                     611, 2799, 614, 2799, 623, 2790, 623, 2791, 632, 2786, 641, 2781, 646, 2772, 646, 2768, 656, 2762,
                     673, 2761, 692, 2763, 702, 2775, 719, 2808, 731, 2820, 745, 2821, 757, 2830, 752, 2822, 757, 2827,
                     765, 2836, 760, 2841, 769, 2812, 765, 2804, 779, 2819, 788, 2922, 777, 2920, 767, 2889, 763, 2950,
                     766, 2948, 758, 2931, 760, 2922, 756, 2920, 741, 2924, 743, 2924, 751, 2932, 748, 2931, 758, 2947,
                     752, 2921, 726, 2932, 731, 2945, 733, 2950, 742, 2950, 757, 2968, 754, 2974, 775, 2986, 773, 2997,
                     769, 3001, 760, 2993, 723, 2948, 727, 2939, 716, 2943, 705, 2943, 718, 2951, 724, 2965, 720, 2964,
                     711, 2955, 697, 2965, 708, 2968, 720, 2977, 718, 2982, 710, 2973, 702, 2973, 688, 2986, 677, 3001,
                     662, 2980, 636, 3006, 661, 2997, 626, 3016, 655, 3030, 647, 3026, 625, 3031, 633, 3041, 633, 3039,
                     644, 3054, 645, 3055, 612, 3062, 638, 3064, 619, 3066, 627, 3073, 636, 3079, 637, 3079, 615, 3097,
                     615, 3086, 614, 3079, 627, 3086, 642, 3138, 673, 3126, 688, 3114, 701, 3114, 709, 3123, 714, 3127,
                     706, 3132, 693, 3143, 678, 3156, 686, 3162, 676, 3188, 663, 3189, 651, 3179, 639, 3189, 647, 3191,
                     661, 3199, 659, 3194, 669, 3203, 669, 3190, 672, 3158, 694, 3174, 695, 3166, 703, 3179, 709, 3169,
                     713, 3162, 703, 3152, 705, 3155, 730, 3142, 737, 3149, 722, 3150, 714, 3128, 741, 3127, 732, 3133,
                     724, 3124, 731, 3109, 733, 3109, 745, 3099, 743, 3071, 760, 3056, 766, 3039, 765, 3000, 790, 2978,
                     791, 2965, 802, 2951, 798, 2929, 805, 2908, 818, 2908, 841, 2954, 817, 2977, 812, 3071, 771, 3080,
                     767, 3146, 750, 3180, 749, 3193, 741, 3205, 741, 3204, 727, 3218, 717, 3209, 729, 3208, 737, 3221,
                     737, 3232, 740, 3252, 747, 3276, 744, 3278, 729, 3264, 721, 3259, 736, 3256, 726, 3246, 723, 3252,
                     713, 3250, 699, 3259, 692, 3270, 680, 3268, 688, 3276, 686, 3274, 677, 3268, 666, 3270, 658, 3270,
                     666, 3277, 681, 3280, 670, 3288, 674, 3284, 682, 3295, 670, 3307, 676, 3307, 687, 3317, 667, 3316,
                     655, 3325, 660, 3316, 685, 3326, 677, 3323, 686, 3327, 695, 3328, 707, 3315, 720, 3314, 734, 3325,
                     737, 3337, 734, 3328, 731, 3339, 733, 3334, 722, 3342, 722, 3341, 710, 3344, 699, 3358, 707, 3367,
                     704, 3378, 692, 3379, 677, 3371, 668, 3382, 673, 3389, 686, 3400, 687, 3411, 688, 3414, 675, 3405,
                     663, 3406, 649, 3406, 657, 3423, 670, 3421, 654, 3426, 680, 3426, 669, 3428, 680, 3427, 669, 3429,
                     679, 3430, 655, 3438, 684, 3440, 663, 3444, 683, 3452, 672, 3450, 648, 3441, 646, 3440, 632, 3444,
                     645, 3453, 632, 3457, 671, 3469, 662, 3468, 648, 3465, 639, 3469, 648, 3482, 657, 3485, 643, 3478,
                     633, 3485, 642, 3485, 631, 3491, 648, 3499, 648, 3504, 657, 3507, 649, 3498, 638, 3509, 647, 3505,
                     618, 3513, 649, 3521, 655, 3529, 640, 3528, 648, 3539, 654, 3538, 676, 3547, 684, 3548, 676, 3556,
                     661, 3547, 661, 3566, 646, 3572, 632, 3578, 622, 3579, 632, 3580, 617, 3581, 636, 3589, 632, 3591,
                     619, 3595, 611, 3593, 624, 3596, 611, 3594, 622, 3603, 640, 3612, 637, 3616, 624, 3619, 631, 3619,
                     616, 3622, 626, 3628, 617, 3622, 608, 3631, 604, 3626, 628, 3635, 629, 3646, 633, 3649, 618, 3659,
                     623, 3660, 614, 3664, 624, 3672, 625, 3675, 621, 3675, 601, 3682, 624, 3682, 614, 3684, 625, 3688,
                     617, 3696, 625, 3696, 610, 3696, 624, 3705, 623, 3708, 605, 3711, 619, 3725, 619, 3717, 615, 3714,
                     605, 3712, 597, 3719, 609, 3723, 594, 3725, 602, 3729, 615, 3731, 601, 3744, 603, 3742, 585, 3745,
                     604, 3755, 603, 3759, 593, 3753, 578, 3759, 594, 3769, 599, 3769, 582, 3774, 591, 3786, 587, 3787,
                     573, 3788, 562, 3789, 588, 3791, 576, 3791, 585, 3795, 575, 3807, 575, 3805, 567, 3808, 577, 3806,
                     567, 3811, 576, 3808, 566, 3811, 575, 3810, 566, 3813, 575, 3813, 566, 3818, 578, 3821, 566, 3813,
                     562, 3815, 545, 3815, 558, 3820, 564, 3820, 554, 3822, 563, 3824, 555, 3827, 564, 3833, 556, 3831,
                     564, 3840, 549, 3843, 567, 3844, 558, 3848, 568, 3874, 569, 3871, 561, 3893, 547, 3887, 537, 3894,
                     548, 3903, 539, 3915, 532, 3901, 517, 3915, 531, 3914, 521, 3932, 517, 3924, 517, 3923, 494, 3931,
                     505, 3942, 489, 3939, 504, 3951, 499, 3951, 485, 3953, 490, 3953, 501, 3952, 511, 3951, 522, 3956,
                     514, 3955, 525, 3963, 520, 3964, 528, 3981, 513, 3983, 491, 3983, 507, 3980, 517, 3999, 530, 4002,
                     518, 4010, 512, 4007, 520, 4015, 515, 4006, 521, 4020, 536, 4022, 527, 4022, 537, 4053, 542, 4062,
                     541, 4069, 516, 4081, 505, 4085, 489, 4095, 491, 4118, 501, 4127, 503, 4139, 498, 4176, 494, 4195,
                     485, 4203, 471, 4201, 484, 4224, 482, 4223, 473, 4224, 476, 4224, 589, 4215, 588, 4206, 596, 4176,
                     603, 4128, 621, 4095, 627, 4080, 631, 4069, 636, 4050, 635, 4033, 648, 4010, 651, 3998, 657, 3997,
                     648, 3976, 661, 3952, 670, 3936, 670, 3906, 681, 3854, 682, 3844, 675, 3832, 683, 3837, 677, 3818,
                     677, 3826, 689, 3840, 691, 3915, 686, 4095, 635, 4224, 592, 4224, 4224, -128, 4224, -128, 4224},
    std::vector<int>{2049, 3181, 2049, 3183, 2037, 3194, 2047, 3190, 2110, 3142, 2156, 3116, 2224, 3084, 2223, 3073,
                     2217, 3057, 2208, 3059, 2196, 3054, 2207, 3053, 2204, 3040, 2195, 3037, 2186, 3045, 2186, 3034,
                     2177, 3037, 2169, 3036, 2165, 3044, 2169, 3055, 2177, 3048, 2175, 3061, 2174, 3073, 2174, 3084,
                     2162, 3092, 2155, 3102, 2126, 3123, 2118, 3121, 2109, 3127, 2103, 3102, 2102, 3114, 2075, 3126,
                     2079, 3144, 2069, 3142, 2069, 3151, 2059, 3159, 2049, 3181, 2049, 3181},
    std::vector<int>{1578, 3811, 1580, 3811, 1580, 3819, 1575, 3827, 1566, 3832, 1558, 3844, 1563, 3846, 1551, 3846,
                     1555, 3864, 1567, 3883, 1601, 3834, 1675, 3768, 1675, 3752, 1665, 3738, 1662, 3717, 1656, 3727,
                     1658, 3712, 1643, 3707, 1641, 3717, 1643, 3725, 1653, 3726, 1645, 3740, 1642, 3750, 1647, 3758,
                     1648, 3748, 1658, 3750, 1657, 3738, 1659, 3751, 1647, 3759, 1635, 3756, 1620, 3755, 1633, 3767,
                     1625, 3770, 1611, 3773, 1621, 3786, 1610, 3776, 1612, 3786, 1598, 3815, 1589, 3821, 1578, 3811,
                     1578, 3811},
    std::vector<int>{2304, 2930, 2298, 2928, 2312, 2926, 2301, 2920, 2292, 2925, 2295, 2914, 2304, 2919, 2313, 2926,
                     2324, 2928, 2335, 2918, 2331, 2908, 2320, 2918, 2307, 2911, 2321, 2916, 2329, 2906, 2316, 2904,
                     2319, 2896, 2308, 2899, 2303, 2891, 2290, 2890, 2287, 2880, 2286, 2892, 2283, 2911, 2296, 2905,
                     2288, 2907, 2288, 2922, 2279, 2926, 2287, 2927, 2292, 2938, 2303, 2934, 2313, 2929, 2304, 2930,
                     2304, 2930},
    std::vector<int>{2316, 2895, 2317, 2895, 2316, 2901, 2331, 2901, 2332, 2889, 2321, 2885, 2323, 2898, 2325, 2889,
                     2315, 2882, 2308, 2896, 2316, 2895, 2316, 2895},
    std::vector<int>{2304, 2850, 2300, 2851, 2311, 2859, 2323, 2868, 2339, 2871, 2335, 2861, 2341, 2873, 2341, 2885,
                     2350, 2887, 2341, 2887, 2335, 2895, 2336, 2906, 2344, 2910, 2369, 2866, 2369, 2856, 2357, 2828,
                     2348, 2824, 2349, 2840, 2346, 2854, 2335, 2839, 2339, 2853, 2331, 2857, 2317, 2851, 2304, 2850,
                     2304, 2850},
    std::vector<int>{1714, 3583, 1714, 3583, 1720, 3595, 1719, 3607, 1709, 3606, 1706, 3619, 1721, 3630, 1725, 3638,
                     1722, 3649, 1714, 3654, 1712, 3664, 1702, 3665, 1698, 3688, 1695, 3700, 1681, 3706, 1682, 3717,
                     1697, 3707, 1743, 3631, 1782, 3583, 1797, 3564, 1775, 3544, 1780, 3552, 1781, 3560, 1765, 3583,
                     1759, 3592, 1749, 3589, 1757, 3587, 1747, 3583, 1735, 3586, 1734, 3595, 1744, 3599, 1746, 3591,
                     1746, 3603, 1752, 3595, 1747, 3605, 1755, 3598, 1732, 3633, 1742, 3604, 1731, 3596, 1724, 3583,
                     1720, 3574, 1712, 3574, 1714, 3583, 1714, 3583},
    std::vector<int>{1537, 3873, 1553, 3869, 1546, 3859, 1536, 3859, 1508, 3867, 1500, 3864, 1502, 3854, 1492, 3859,
                     1475, 3878, 1495, 3855, 1456, 3827, 1419, 3828, 1405, 3876, 1410, 3886, 1420, 3894, 1451, 3893,
                     1461, 3898, 1493, 3895, 1537, 3873, 1537, 3873},
    std::vector<int>{2547, 2560, 2550, 2563, 2537, 2585, 2527, 2605, 2518, 2609, 2507, 2631, 2495, 2652, 2489, 2656,
                     2489, 2671, 2477, 2683, 2477, 2691, 2471, 2699, 2463, 2703, 2459, 2719, 2447, 2724, 2448, 2738,
                     2438, 2750, 2436, 2758, 2421, 2770, 2414, 2787, 2405, 2799, 2394, 2808, 2383, 2815, 2375, 2815,
                     2384, 2825, 2403, 2810, 2470, 2722, 2559, 2562, 2620, 2456, 2658, 2368, 2685, 2336, 2667, 2324,
                     2658, 2346, 2649, 2342, 2648, 2334, 2648, 2310, 2648, 2332, 2638, 2337, 2640, 2347, 2649, 2350,
                     2646, 2368, 2642, 2376, 2641, 2384, 2626, 2389, 2634, 2389, 2639, 2397, 2630, 2395, 2638, 2399,
                     2630, 2395, 2638, 2400, 2627, 2396, 2636, 2403, 2624, 2397, 2629, 2406, 2626, 2422, 2621, 2431,
                     2617, 2442, 2609, 2453, 2618, 2451, 2609, 2458, 2607, 2469, 2589, 2498, 2569, 2511, 2565, 2519,
                     2561, 2527, 2552, 2536, 2548, 2550, 2547, 2560, 2547, 2560},
    std::vector<int>{2107, 3073, 2110, 3083, 2098, 3093, 2107, 3098, 2117, 3090, 2127, 3086, 2144, 3086, 2132, 3073,
                     2122, 3073, 2113, 3059, 2107, 3073, 2107, 3073},
    std::vector<int>{2117, 3120, 2125, 3122, 2128, 3114, 2137, 3112, 2142, 3101, 2156, 3099, 2164, 3083, 2151, 3082,
                     2144, 3090, 2129, 3094, 2121, 3093, 2106, 3103, 2117, 3120, 2117, 3120},
    std::vector<int>{2303, 2981, 2303, 2981, 2289, 2967, 2265, 2977, 2273, 2988, 2284, 2993, 2275, 3005, 2265, 3009,
                     2254, 3021, 2238, 3022, 2226, 3010, 2229, 3025, 2218, 3031, 2210, 3035, 2215, 3043, 2218, 3034,
                     2235, 3027, 2230, 3041, 2216, 3043, 2232, 3064, 2286, 3012, 2303, 2989, 2338, 2945, 2344, 2928,
                     2330, 2936, 2305, 2942, 2307, 2954, 2313, 2941, 2320, 2951, 2321, 2943, 2329, 2947, 2322, 2957,
                     2309, 2959, 2307, 2967, 2303, 2981, 2303, 2981},
    std::vector<int>{2304, 2858, 2292, 2854, 2291, 2864, 2301, 2863, 2297, 2875, 2305, 2877, 2303, 2885, 2316, 2875,
                     2324, 2870, 2311, 2866, 2304, 2858, 2304, 2858},
    std::vector<int>{2175, 3002, 2173, 3007, 2185, 3008, 2183, 3000, 2175, 3001, 2181, 2991, 2179, 2983, 2163, 2987,
                     2166, 2997, 2174, 2998, 2164, 3000, 2152, 2991, 2175, 3002, 2175, 3002},
    std::vector<int>{2175, 3022, 2166, 3019, 2153, 3026, 2150, 3017, 2150, 3025, 2141, 3029, 2145, 3038, 2144, 3048,
                     2154, 3046, 2153, 3037, 2159, 3031, 2175, 3031, 2184, 3030, 2175, 3022, 2175, 3022},
    std::vector<int>{2265, 2953, 2270, 2950, 2262, 2950, 2263, 2958, 2254, 2963, 2253, 2979, 2257, 2969, 2261, 2979,
                     2269, 2970, 2279, 2966, 2265, 2953, 2265, 2953},
    std::vector<int>{2229, 2928, 2237, 2939, 2236, 2924, 2239, 2920, 2239, 2933, 2250, 2928, 2241, 2922, 2239, 2914,
                     2224, 2900, 2237, 2914, 2228, 2925, 2229, 2928, 2229, 2928},
    std::vector<int>{2531, 2473, 2525, 2476, 2533, 2468, 2520, 2466, 2521, 2474, 2511, 2503, 2523, 2492, 2541, 2488,
                     2546, 2491, 2546, 2483, 2531, 2485, 2531, 2473, 2531, 2473},
    std::vector<int>{2547, 2526, 2546, 2519, 2535, 2516, 2538, 2524, 2529, 2519, 2533, 2527, 2536, 2537, 2528, 2541,
                     2544, 2538, 2547, 2526, 2547, 2526},
    std::vector<int>{2559, 646, 2550, 647, 2530, 671, 2529, 697, 2538, 704, 2533, 715, 2535, 738, 2524, 751, 2521, 785,
                     2513, 810, 2503, 818, 2489, 815, 2463, 835, 2471, 858, 2468, 882, 2464, 892, 2456, 895, 2449, 908,
                     2453, 922, 2462, 930, 2485, 919, 2505, 916, 2520, 900, 2531, 898, 2552, 886, 2560, 884, 2615, 852,
                     2616, 840, 2628, 833, 2636, 842, 2627, 854, 2617, 854, 2619, 865, 2643, 837, 2652, 831, 2664, 820,
                     2674, 816, 2682, 802, 2712, 771, 2746, 731, 2743, 719, 2717, 683, 2715, 673, 2723, 676, 2715, 669,
                     2715, 660, 2716, 652, 2707, 638, 2697, 637, 2678, 644, 2662, 643, 2651, 651, 2637, 654, 2633, 651,
                     2625, 651, 2604, 659, 2596, 658, 2581, 650, 2572, 651, 2559, 646, 2559, 646},
    std::vector<int>{3840, 653, 3841, 653, 3826, 650, 3818, 645, 3809, 641, 3819, 648, 3806, 645, 3795, 656, 3773, 665,
                     3743, 671, 3751, 672, 3733, 681, 3720, 678, 3718, 689, 3706, 682, 3697, 685, 3700, 693, 3690, 698,
                     3687, 688, 3677, 692, 3675, 702, 3671, 694, 3663, 697, 3650, 707, 3642, 702, 3634, 703, 3605, 707,
                     3584, 716, 3575, 722, 3547, 733, 3560, 725, 3551, 723, 3565, 716, 3553, 712, 3534, 720, 3534, 728,
                     3523, 732, 3506, 733, 3494, 738, 3485, 742, 3474, 746, 3478, 750, 3457, 750, 3443, 767, 3440, 780,
                     3472, 767, 3583, 734, 3667, 710, 3750, 679, 3808, 665, 3826, 667, 3825, 656, 3839, 657, 3866, 655,
                     3893, 663, 3908, 659, 3876, 649, 3840, 653, 3840, 653},
    std::vector<int>{3327, 741, 3284, 746, 3242, 750, 3195, 745, 3180, 758, 3201, 758, 3253, 763, 3326, 764, 3372, 759,
                     3438, 756, 3440, 742, 3424, 744, 3381, 737, 3379, 740, 3358, 740, 3357, 740, 3349, 740, 3349, 751,
                     3348, 740, 3346, 751, 3346, 740, 3342, 740, 3342, 751, 3341, 740, 3338, 741, 3338, 751, 3337, 741,
                     3327, 741, 3327, 741},
    std::vector<int>{3282, 702, 3284, 696, 3273, 688, 3265, 699, 3272, 709, 3273, 721, 3281, 722, 3281, 712, 3290, 714,
                     3292, 696, 3282, 702, 3282, 702},
    std::vector<int>{3762, 662, 3763, 662, 3767, 654, 3783, 654, 3785, 646, 3786, 638, 3774, 639, 3771, 648, 3760, 640,
                     3747, 652, 3742, 653, 3742, 663, 3762, 662, 3762, 662},
    std::vector<int>{3071, 703, 3071, 703, 3080, 711, 3080, 720, 3082, 728, 3073, 735, 3082, 741, 3092, 703, 3079, 655,
                     3064, 657, 3068, 669, 3065, 677, 3058, 701, 3071, 703, 3071, 703},
    std::vector<int>{3881, 637, 3871, 642, 3885, 647, 3904, 647, 3912, 642, 3904, 642, 3906, 630, 3915, 631, 3914, 626,
                     3903, 626, 3893, 617, 3891, 625, 3881, 624, 3881, 635, 3879, 627, 3871, 626, 3861, 638, 3870, 641,
                     3881, 637, 3881, 637}
};

static const std::vector<std::vector<int>> rectangleData = {
    std::vector<int>{0,0,20,0,20,10,0,10}};

static const std::vector<std::vector<int>> degenerated1Data = {
    std::vector<int>{0, 0, 1, 0, 2, 0, 0, 0}};

static const std::vector<std::vector<int>> degenerated2Data = {
    std::vector<int>{0, 0, 1, 0, 1, 1, 1, 0, 0, 0}};

osmscout::Area testArea(const std::vector<std::vector<int>> &data)
{
  osmscout::Area area;
  for (const auto &ringData: data) {
    assert(ringData.size() % 2 == 0);
    osmscout::Area::Ring ring;
    ring.SetRing(osmscout::Area::outerRingId);
    ring.nodes.reserve(ringData.size() / 2);
    for (size_t i=0; i<ringData.size(); i+=2){
      ring.nodes.push_back(osmscout::Point(0, osmscout::GeoCoord(ringData[i], ringData[i+1])));
    }
    area.rings.emplace_back(std::move(ring));
  }

  return area;
}

std::ostream& operator<<(std::ostream &os, const osmscout::GeoCoord &value)
{
  os << value.GetDisplayText();
  return os;
}

namespace Catch {
template<>
struct StringMaker<osmscout::GeoCoord> {
  static std::string convert(const osmscout::GeoCoord &value)
  {
    return value.GetDisplayText();
  }
};
}

TEST_CASE("compute polygon center of simple rectangle")
{
  osmscout::log.Debug(true);
  osmscout::log.Info(true);
  osmscout::log.Warn(true);
  osmscout::log.Error(true);

  auto rectangle = testArea(rectangleData);

  // finds pole of inaccessibility for water1 and precision 1
  REQUIRE(PolygonCenter(rectangle, 1.0) == osmscout::GeoCoord(10, 5));
}

TEST_CASE("compute polygon center of multi-ring areas")
{
  osmscout::log.Debug(true);
  osmscout::log.Info(true);
  osmscout::log.Warn(true);
  osmscout::log.Error(true);

  auto water1 = testArea(water1Data);
  auto water2 = testArea(water2Data);

  // finds pole of inaccessibility for water1 and precision 1
  REQUIRE(PolygonCenter(water1, 1.0) == osmscout::GeoCoord(3865.85009765625, 2124.87841796875));

  // finds pole of inaccessibility for water1 and precision 50
  REQUIRE(PolygonCenter(water1, 50.0) == osmscout::GeoCoord(3854.296875, 2123.828125));

  // finds pole of inaccessibility for water2 and default precision 1
  REQUIRE(PolygonCenter(water2) == osmscout::GeoCoord(3263.5, 3263.5));
}

TEST_CASE("compute polygon center of degenerated areas")
{
  osmscout::log.Debug(true);
  osmscout::log.Info(true);
  osmscout::log.Warn(true);
  osmscout::log.Error(true);

  auto degenerated1 = testArea(degenerated1Data);
  auto degenerated2 = testArea(degenerated2Data);

  // works on degenerate polygons
  REQUIRE(PolygonCenter(degenerated1) == osmscout::GeoCoord(0, 0));
  REQUIRE(PolygonCenter(degenerated2) == osmscout::GeoCoord(0, 0));
}
